7-26 求素数个数——朴素筛

求素数的个数。本题要求编写一个程序，求1~n的素数个数。 要求至少给出两种解法，对于相同的n，给出这两种解法的结果，通过相关数据进行测试，目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。

输入格式:
输入在一行中给出1个整数n(<= 10 000 000)。

输出格式:
对每一组输入，在一行中输出1~n的素数个数。

输入样例1:
5
输出样例1:
3
输入样例2:
14
输出样例2:
6

分析

1. 直接暴力判断TLE两个点，if (i % 2 == 0 && i != 2) continue，加了这个条件挽救了一个点，但是还有一个测试点TLE；
2. 前面写过线性筛了，这里用个朴素筛，j从i+i开始，j每次加i，把这些元素全筛掉；虽然比线性筛慢，但是容易理解，好写；

#include

using namespace std;

int primes[10000005], cnt;     // primes[]存储所有素数
bool st[10000005];         // st[x]存储x是否被筛掉

void getPrimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main() {
    int n;
    cin >> n;
    getPrimes(n);
    cout << cnt;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23