复杂度O(n)
算法步骤
1、先初始化number数组全为true，代表每个数都为素数，（0和1手动修改为false,因为它们很明显不是素数），然后从数字2开始遍历（显然2是素数）
2、将number为true的放入prime数组中，并使下标+1，然后再遍历prime，将prime中的数的 i 倍的number改为false，减少后面的判断，注意边界条件prime * i <=n
3、注意还有一个特判条件如果prime能被i整除，即i%prime==0，我们就不再深究下去了，然后重复（2）
#include<iostream> #include<cstring> using namespace std; const int maxn = 1e6+10; //=================== int prime[maxn]; bool number[maxn]; int n,cnt; void isprime(int n){ //1~n的素数 memset(number, true, sizeof number); number[0]=number[1] = false; cnt = 0; for (int i = 2; i <= n; i++){ if (number[i]) prime[cnt++] = i; for (int j = 0; j < cnt&&prime[j] * i <= n; j++){ number[prime[j] * i] = false; if (i%prime[j] == 0) break; } } } int main() { cin >> n; isprime(n); for (int i = 0; i < cnt; i++){ cout << prime[i] << endl; } return 0; }
原文：https://www.cnblogs.com/looeyWei/p/10498341.html
