• 前言
• 正题
• 如何保证
• 证明
• 代码注释

前言

以前学过的Eratosthenes筛法，时间复杂度是$O(n log n)$的。
然而对于五千万左右的数据，Eratosthenes就会华丽爆炸。

于是要用更加高级的算法——欧拉筛。

正题

Eratosthenes慢在对于一个合数，它会被所有比它小的质因子筛过。
而欧拉筛则可以保证，每个合数只会被它最小的质因子筛。
这样均摊复杂度为$O(N)$。

如何保证

欧拉筛每次用一个数i，和之前晒出的质数相乘来判断合数。
如果$prime[j]|i$，那么可以直接跳出。
因为$i*prime[j+1]$一定会被prime[j]筛。
以此均摊复杂度。

证明

$∵prime[j]|i$
$∴i=k*prime[j]$
$∵i*prime[j+1]=k*prime[j]*prime[j+1]$
$∴i*prime[j+1]=k'*prime[j]$
∴i∗prime[j+1]一定会被prime[j]筛掉。 $∴i*prime[j+1]一定会被prime[j]筛掉。$

代码&注释

#include 
#include 
#define fo(a,b,c) for (a=b; a<=c; a++)
#define n 10000000//范围
using namespace std;
bool print=false;//是否输出
int i,j,k;
bool f[1000000001];
int p[100000001];//质数表，p[0]为长度__attribute__((optimize("-O2")))//O2优化233
int main()
{fo(i,2,n)//枚举一个数{if (!f[i])//如果没有被筛过，说明是质数p[++p[0]]=i;fo(j,1,p[0])//枚举筛过的质数{k=i*p[j];if (k>n)break;f[k]=true;if (!(i%p[j]))//重点优化，防止多筛break;}}if (!print)return 0;fo(i,1,p[0]){printf("%10d",p[i],' ');if (!(i%11))printf("\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！