LeetCode 204. Count Primes(线性素数筛)

题意：求[1-n)中的质数。

题解：判断一个数是否是素数，很简单，

代码语言：javascript复制

for(int i=2;i * i < x ;i  )
{
    if(x%i==0)
        return false;
}
return true;

但是这样做明显会超时，所以我们用素数筛，来快速的求出1-n的所有素数。素数筛的原理，就是所有素数的倍数都是合数，求出一个素数，就把它的倍数都筛掉。

但是这样有一个问题，就是会筛两次，比如素数2会把30给筛掉，5 也会把30给筛掉。所以这个效率就是O(n)的，O(n)效率的素数筛，是欧拉素数筛。

它的核心思想，我会写另一篇博客介绍下。

代码语言：javascript复制

class Solution {
public:
    int E[5000005];
    int prime[1000005];
    int check[5000005];
    int pos=0;
    int countPrimes(int n) {
        
        Euler(n);
        
        return pos;
       
        
    }
    
    void Euler(int n)
    {
        check[1]=0;
        
        for(int i=2;i<n;i  )
        {
            if(!check[i])
            {
                prime[pos  ]=i;
                E[i] = i-1;
            }
            
            for(int j=0;j<pos;j  )
            {
                if(prime[j]*i>=n)
                    break;
                check[prime[j]*i]=1;
                if(i%prime[j]==0)
                {
                    E[i*prime[j]]=E[i]*prime[j];
                    break;
                }
                else
                    E[i*prime[j]]=E[i]*(prime[j]-1);
            }
        }
    }
    
};

博客 效率 原理

0 人点赞