3292-Semi-prime H-numbers

問題（外部リンク）

3292 -- Semi-prime H-numbers

実装の概要

この問題では数字はの形で表されるH-numberしか現れません。
H-primeかどうかの判定は通常の整数に対するエラトステネスの篩を改修することで実現できますが、H-semi-primeかどうかの判定は困難です。この篩では掛ける数まで素数かどうかは考慮していないからです。
そのため、この実装ではやや強引ですが2回篩にかけます。即ち、1回目はH-numberがH-primeかどうかを、2回目はH-compositeの中にH-semi-primeが存在するかを判断するためにループを回します。
なお、もともとH-numberしか考えないので1,000,001までの全ての値について配列を用意する必要はありません。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//-1: unit 0 : prime 1 : semi-prime 2 : other-composite
		int type[] = new int[250001];
		type[0] = -1;

		//素数かどうかを判定するための初期化
		for(int i = 1; i < type.length ; i++){
			if(type[i] == 0){
				for(int j = 5; (4*i + 1)*j <= 1000001 ; j += 4){
					int tmpN = ((4*i + 1)*j - 1)/4;
					type[tmpN] = 2;
				}
			}
		}

		//こちらではsemi-primeかどうかを判定
		for(int i = 1; i < type.length ; i++){
			if(type[i] == 0){
				for(int j = 5; (4*i+1)*j <= 1000001 ; j += 4){
					int tmpN = ((4*i+1)*j - 1)/4;
					//素数と掛けたものならsemi-prime
					if(type[j/4] == 0){
						type[tmpN] = 1;

					}
					else {
						type[tmpN] = 2;
					}
				}
			}
		}

		while(true){

			int n = Integer.parseInt(br.readLine());

			if(n == 0){
				break;
			}

			int result = 0;
			//semi-primeならresult加算
			for(int i = 1; i*4+1 <= n ; i++){
				if(type[i] == 1){
					result++;
				}
			}

			System.out.println(n+" "+result);
		}
	}

}