AOJ 0009 Prime Number

問題概要

整数nが与えられるので、n以下の素数の数を出力せよ。
なお、素数とは、「1と自分自身でしか割り切れない正の整数のうち1を除いたもの」である。

制約

• 1 ≤ n ≤ 999999

解法

エラトステネスの篩 + 累積和

エラトステネスの篩については、wikipedia(エラトステネスの篩 - Wikipedia)などを参考。
実装は、以下のようになる。 O(n log log n) である。

#define MAX 1000000

int prime[MAX]; // 全て1で初期化する。
prime[0] = prime[1] = 0;
for (int i = 2; i < MAX; i++) {
    if (prime[i]) {
        for (int j = 2*i; j < MAX; j += i) {
            prime[j] = 0;
        }
    }
}

エラトステネスの篩で埋めた、素数かどうかを判定する配列を用いて累積和を求める。
累積和とは、
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 .... を
0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 .... とするイメージ。

prime[i] = prime[i] + prime[i-1] (i > 0)
のようにすると累積和を求めることができる。

後は、与えられたnに対して、prime[n]を出力すれば良いことになる。

コード

#include <iostream>

using namespace std;
 
#define MAX 1000000
 
int main()
{
    int prime[MAX];
    fill(prime, prime + MAX, 1);
    prime[0] = prime[1] = 0;
    for (int i = 2; i < MAX; i++) {
        if (prime[i]) {
            for (int j = 2*i; j < MAX; j += i) {
                prime[j] = 0;
            }
        }
    }
    
    for (int i = 1; i < MAX; i++) {
	prime[i] = prime[i] + prime[i-1];
    }
    
    int N;
    while (cin >> N) {
	cout << prime[N] << endl;
    }
    return 0;
}