AOJ0009 Prime Number

問題

Prime Number | Aizu Online Judge

コメント

素数ときたらエラトステネスの篩。復習しながらコードを書いたので、今度は自力でコードを書けるようにする。
ソース1はエラトステネスのみ。ソース2はエラトステネスと累積和を使用したもの。
どっちのほうが早いかは分からない。

ソース1(エラトステネス)

//エラトステネスのみ
public class Main {
	boolean[] prime;

	void run() {
		Scanner sc = new Scanner(System.in);

		era(1000000);

		while (sc.hasNext()) {
			int n = sc.nextInt();
			int count = 0;
			for (int i = 2; i <= n; i++) {
				if (prime[i]) {
					count++;
				}
			}
			System.out.println(count);
		}
		sc.close();
	}

	public void era(int n) {
		prime = new boolean[n + 1];
		Arrays.fill(prime, true);
		prime[0] = prime[1] = false;

		for (int i = 2; i * i <= n; i++) {
		　　if (prime[i]) {
			for (int j = i + i; j <= n; j += i) {
			　　prime[j] = false;
			}
		　　}
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

ソース2(エラトステネス＋累積和)

//エラトステネス(範囲制限なし)+累積和
public class Main {
	boolean[] prime;
	int[] sum;

	void run() {
		Scanner sc = new Scanner(System.in);

		era(1000000);

		while (sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(sum[n]);
		}
		sc.close();
	}

	public void era(int n) {
		prime = new boolean[n + 1];
		sum = new int[n + 1];

		Arrays.fill(prime, true);
		prime[0] = prime[1] = false;

		int count = 0;

		for (int i = 2; i <= n; i++) {
		　　if (prime[i]) {
			count++;
			for (int j = i + i; j <= n; j += i) {
			　　prime[j] = false;
			}
		　　}
		　　sum[i] += count;
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}