PHP做网站案例教程,广州建筑设计公司,军事最新消息今天,咨询管理在传统的素数筛法中#xff0c;我们使用了对于每一个数n#xff0c;在 1~(√n) 范围内进行取模检查#xff0c;这样逐一判断的复杂度为n(√n)。但如果我们需要更快的筛法时怎么办#xff1f;于是著名的欧拉筛诞生了。它能将复杂度降为**O(n)**级别。1.关键理解#xff1a;…在传统的素数筛法中我们使用了对于每一个数n在 1~(√n) 范围内进行取模检查这样逐一判断的复杂度为n(√n)。但如果我们需要更快的筛法时怎么办于是著名的欧拉筛诞生了。它能将复杂度降为**O(n)**级别。1.关键理解欧拉筛的原理是保证在 2~n 范围中的每一个合数都能被唯一分解成它的最小质因数与除自己外最大的因数相乘的形式。因此我们枚举2~n中的每一个数作为筛法中的“除自己外的最大因数”如果它未被标记为合数就先将它放入素数表内再将这个最大因数与素数表中已经找到的素数作为最小质因数相乘将得到的这些数标记为合数。最后输出得到的素数表即可。但是我们如何保证每个合数都被唯一分解解决方法如下当此时取出的素数表中的素数(即枚举的最小质因子)整除于当前枚举的合数时我们就停止循环素数表开始枚举下一个合数。证明如下设当前枚举的最小质因子prime[i]整除于合数n时即我们要筛掉合数 n*prime[i] 如果我们此时不退出继续枚举下一个素数prime[i1]对于将要筛掉的合数 n*prime[i1] 由于插入顺序从小到大则 prime[i1]prime[i]。由于prime[i]整除于合数n所以必然合数 n*prime[i1] 还可以被分解为$$(\frac{n}{prime[i]}*prime[i1])*prime[i]$$显然在上面的分解方式中我们将要筛掉的合数分解为更小的质因子 prime[i] 这不符合我们对于每一个数被唯一分解的要求所以我们可在代码中加入一行判断整除关系的代码进行优化。2.代码实现#include #include #include #include #include #include #include #include #include #include #include using namespace std;inline void read(int x){x0;int f1;char chgetchar();while(ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x1)(x3)(ch^48);chgetchar();}x*f;}bool IsPrime[100005];int prime[50005];int main(int argc, char const *argv[]){int n,top1;memset(IsPrime,1,sizeof(IsPrime));read(n);for(int i2;in;i){if(IsPrime[i])prime[top]i,top;for(int j1;j{if(i*prime[j]n)break;IsPrime[i*prime[j]]0;if(i%prime[j]0)break;}}coutfor(int i1;icoutreturn 0;}
