AOJ 0009 Prime Number
制約
- 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; }