素数判定（素数筛法）（欧拉）_素数判断公式

作者：在线问答5 | 2024-07-01 04:43:40

踩

素数判断公式

这里主要说一下 素数筛法，该方法可以快速的选取出1~N数字中的所有素数。时间复杂度 远小于O(N*sqrt(N))

方法为：从2开始，往后所有素数的倍数都不是素数。最后剩下的数都是素数。

再说说欧拉公式，用来解决所有小于n中的数字有多少个与n互质，用Ψ(n)表示。

Ψ(n)=n*(1-1/q1)*(1-1/q2)*……*(1-1/qk),n为和数，其中qi为n的质因数。
Ψ(n)=n-1，n为质数

下面有网上的几种表示，


<span style="color:#ff6666;">// 1：这是最原始的筛法，还有待优化 
</span>#define Max 1000000
bool prime[Max];
void IsPrime(){
     prime[0]=prime[1]=0;prime[2]=1;
     for(int i=3;i<max;i++)
        prime[i]=i%2==0?0:1;
     int t=(int)sqrt(Max*1.0);
     for(int i=3;i<=t;i++)
       if(prime[i])
         for(int j=i;j<Max;j+=i)
            prime[j]=0;
}
<span style="color:#ff6666;">//2：优化后的筛法&

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/775094