Problem：找出小于等于n的所有素数的个数。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int maxn = 1e6;
int prime[maxn]; // 欧拉线性素数筛,O(n)
bool vis[maxn]; // 标记
int Prime(int n)
{
memset(vis,false,sizeof(vis));
int cnt = 0;
vis[0] = vis[1] = true;
for(int i = 2; i <= n; i )
{
if(!vis[i])prime[cnt ] = i;
for(int j = 0; j < cnt && i*prime[j] <= n; j )
{
vis[i*prime[j]] = true;
if(!(i%prime[j])) break;
}
}
return cnt;
}
int main()
{
int n;
cin >> n;
int ans = 0;
ans = Prime(n);
cout << ans << endl;
return 0;
}if(i % prime[j] == 0) break; 解释： 首先，任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。 当i是prime[j]的整数倍时（i % prime[j] == 0），i*prime[j 1]肯定被筛过，跳出循环。 因为i可以看做prime[j]*某个数， i*prime[j 1]就可以看做 prime[j]*某个数*prime[j 1] 。而 prime[j] 必定小于 prime[j 1]， 所以 i*prime[j 1] 必定已经被 prime[j]*某个数 筛掉，就不用再做了√ 同时我们可以发现在满足程序里的两个条件的时候，prime[j]必定是prime[j]*i的最小质因子。这个性质在某些题里可以用到。 这样就可以在线性时间内找到素数啦~(≧▽≦)/~ 解释转自https://blog.csdn.net/tianwei0822/article/details/78309453
