素数筛法 - 欧拉筛法
素数的筛法有几种，这次主要谈一下欧拉筛法
1.暴力求素数
时间复杂度 : O(n2)
稍微优化一下 ：缩小数据范围从 n 优化到√n
时间复杂度 : 自然也就从 O(n2) 到 O(√n)
2.著名的埃式筛法
时间复杂度 : O(nloglogn)
而要谈的欧拉筛法则是在埃式筛法的基础上再次进行优化
3.欧拉筛法
时间复杂度为: O(n)
#include<cstdio>
using namespace std;
int judge[10000]; //保存 这个数是否为素数
int prime[10000]; //用来保存已经找到的素数
int count; //统计素数的个数
int main()
{
int n;
scanf("%d",&n);
for(int i = 2;i <= n;i++)
{
if(!judge[i]) //如果judge[i] 没有被标记为合数
{
prime[count] = i; //将 i 保存进数组
count++;
} //i*prime[j] 为合数
for(int j = 0;j < count && i*prime[j] <= n;j++) //j 遍历的 是 已保存 的 素数
{
//i*prime[j] 为合数
judge[i*prime[j]] = 1; // 将 i*prime[j] 进行标记
if(i % prime[j] == 0) break; //如果 prime[j] 是 i 的最小质因子，跳出
}
}
printf("%d\n",count);
}
欧拉筛法 比 埃式筛法 的优化 ：
欧拉筛法在埃式筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
质因子：在数论里，某一正整数的质因子指能整除该数的质数整数。
if(i % prime[j] == 0) break; //和埃式筛法最大的不同 ，，避免了重复删除
例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 …
当 i 等于 4 时， 将 8 标记为合数 在这之后 break，因为继续判断的话会将 12 标记
当 i 等于 6 时， 会将 12 进行标记 ，重复标记造成浪费