题目链接

Prime Number Aizu - 0009

思路

$$ 线性筛素数 $$

时间复杂度

$$ O(N) $$

代码

#include <cstdio>
#include <vector>

using namespace std;

class Factor {
public:
    vector<bool> is_prime;
    //pi : min prime factor
    vector<int> prime, pi;
    int sieve(int sz) {
        int cnt = 0;

        is_prime.resize(sz + 1, false);
        pi.resize(sz + 1, 0);
        for (int i = 1; i <= sz; i++) {
            pi[i] = i;
        }
        for (int i = 2; i <= sz; i++) {
            if (pi[i] == i) {
                prime.push_back(i);
                is_prime[i] = true;
                ++cnt;
            }
            for (int j = 0; j < cnt && 1LL * prime[j] * i <= sz; j++) {
                pi[prime[j] * i] = prime[j];
                if (i % prime[j] == 0) {
                    break;
                }
            }
        }
        return cnt;
    }
};

const int MAXN = 1e6 + 10;

int ans[MAXN];

int main() {
    Factor fa;
    int n = 1000000;
    fa.sieve(n);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i - 1] + fa.is_prime[i];
    }
    int x;
    while (~scanf("%d", &x)) {
        printf("%d\n", ans[x]);
    }

    return 0;
}