AcWing 868. 筛质数
本题链接：AcWing 868. 筛质数
本博客提供你本题截图：
诶氏筛法
#include <iostream> #include <algorithm> using namespace std; const int N= 1000010; int primes[N], cnt; bool st[N]; void get_primes(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; } } /*void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if(!st[i]) primes[cnt ++] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }*/ int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
线性筛法
#include <iostream> #include <algorithm> using namespace std; const int N= 1000010; int primes[N], cnt; bool st[N]; /*void get_primes(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; } } */ void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if(!st[i]) primes[cnt ++] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
三、时间复杂度
关于质数各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
