欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求素数个数(埃氏筛法和欧拉筛法)

程序员文章站 2024-03-14 20:54:11
...

求1——n的素数的个数,有以下三种方法:

普通的O(求素数个数(埃氏筛法和欧拉筛法))算法:

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

bool isprime(int x)
{
    if(x<=1)
        return false;
    for(int i=2;i<=sqrt(x+0.5);++i)//+0.5是为了防止精度误差
        if(x%i==0)   return false;
        
    return true;
}

一般来说上面这个已经蛮不错了,可是当n特别大,10^9以上时就有点力不从心了。我们有了下面的埃氏筛法。

埃氏筛法

复杂度:O(loglogn)

埃氏筛法的核心思想就是当我们找到一个素数,那么这个数小于n的所有倍数肯定都不是素数,同时进行标记。

bool prime[maxn];//prime[i]为true表示i为质数
void init()
{
    for(int i=2;i<maxn;i++)//初始化
        prime[i]=true;
    
    for(int i=2;i<maxn;++i)
    {
        if(prime[i])
            for(int j=2*i;j<maxn;j+=i)//把所有i的倍数都进行标记
            {
                prime[j]=false;
            }
    }
}

欧拉筛法

复杂度O(n)

欧拉筛法优化的一点就是改进了埃氏筛法的一点冗余:可以发现,在埃氏筛法中,我们对每一个n都标记了不止一次。比如10,当i=2时,10作为2的倍数被标记一次,当i=5时,10依然是5的倍数,又被多余的标记一次。

欧拉筛法思想:

其基础是  “任何一个合数都可以由两个质数相乘得到”  。那么对于每一个n我们都可以用比它小的某一个质数来标记。

     bool isprime[maxn];//isprime
     int primelistl[maxn];//primelist
     int n;
     int cnt=0;
     scanf("%d",&n);
     for(int i=1;i<=n;++i)
          isprime[i]=true;
     for(int i=2;i<=n;++i)
     {
          if(isprime[i])
          {
               cnt++;    //找到一个素数+1
               primelist[cnt]=i;   //把这个素数添加到素数表里
          }
          for(int j=1;j<=cnt;++j)  //去枚举所有可以到达的质数
          {
               if(i*primelist[j]>n)  //如果已经大于n则break
                    break;
               isprime[i*primelist[j]]=false;
               if(i%primelist[j]==0)   //找到的是最小的质因子
                    break;
          }
     }
     printf("%d\n",cnt);