高效寻找素数

题目

素数：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数

求解[2,n)之间的素数个数。

题解

思路1

这种方法比较好理解，对于[2,n)之间的每个数，直接根据定义判断其是否为素数即可。

bool is_prime(int k)
{
    for(int j=2;j<k;j++)
    {
        if(k%j==0) return false;
    }
    return true;
}

int count_prime(int n)
{
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        if(is_prime(i)) cnt++;
    }
    return cnt;
}

思路2

上述方法的时间复杂度为o(n2)，可以优化一下降低时间复杂度。

第二个for循环，其思路是对于每一个数k，都需要判断k能否被[2,k)中的数整除。

例如12：

12=2x6
12=3x4
12=sqrt(12)xsqrt(12)
12=4x3
12=6x2

可以看到，后面两个数就是前面两个数的反转，临界点就是sqrt(12)，也就是说，在判断前两个以后就无无需判断后两个了。

因此可以将遍历范围缩短到sqrt(n)，这样时间复杂度就变为o(sqrt(n)).

bool is_prime(int k)
{
    for(int j=2;j*j<=k;j++) //注意等号
    {
        if(k%j==0) return false;
    }
    return true;
}

int count_prime(int n)
{
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        if(is_prime(i)) cnt++;
    }
    return cnt;
}

思路3

上面的计算还是有冗余，例如如果已经判断出来2是素数，那么显然，2x2=4不是素数，3x2=6不是素数，4x2=8不是素数.....这些数是不需要判断的，这里借用一个辅助数组

int count_prime(int n)
{
    vector<int>ans(n, true);
    for(int i=2;i<n;i++)
    {
        if(ans[i])
        {
            for(int j=2*i;j<n;j+=i) 
            {
                ans[j]= false;
            }
        }
    }
    int cnt=0;
    for(int k=2;k<n;k++)
    {
        if(ans[k])
        {
            cnt++;
        }     
    }
    return cnt;
}

思路4

上面的计算仍有冗余，例如当i=2，i为素数，那么4=2x2，6=2x3，8=2x4 都会被标记为false。

当i=3时，那么6=3x2，9=3x3也会被标记为false，这里看出6=2x3这块是重复标记的。

可以直接让j从i的平方开始遍历：

i=2时，那么4，6，8会被标记

i=3时，那么9，12，15会被标记

这里6就不会重复标记了。

int count_prime(int n)
{
    vector<int>ans(n, true);
    for(int i=2;i<n;i++)
    {
        if(ans[i])
        {
            for(int j=i*i;j<n;j+=i) 
            {
                ans[j]= false;
            }
        }
    }
    int cnt=0;
    for(int k=2;k<n;k++)
    {
        if(ans[k])
        {
            cnt++;
        }
    }
    return cnt;
}

思路5

看看上一步还有什么问题？

问题出在这

for(int i=2;i<n;i++)

类似于上诉因子的对称性，遍历次数也可以缩小至sqrt(n)

int count_prime(int n)
{
    vector<int>ans(n, true);
    for(int i=2;i*i<n;i++) 
    {
        if(ans[i])
        {
            for(int j=i*i;j<n;j+=i)
            {
                ans[j]= false;
            }
        }
    }
    int cnt=0;
    for(int k=2;k<n;k++)
    {
        if(ans[k])
        {
            cnt++;
        }
    }
    return cnt;
}

总结

方法1，2是一类方法，这种方法通过对数进行遍历求余判断，来计算素数个数，该方法涉及较多的冗余运算，时间复杂度较高。

方法3，4，5是一类方法，利用辅助数组来减小时间复杂度，巧妙的运用了数组的下标，这种方法的时间复杂度大为降低，并无冗余计算，其时间复杂度为o(N*loglogn)。

参考

1.微信公众号： labuladong

2.https://www.cnblogs.com/GuoYuying/p/11674824.html

高效寻找素数

原文：https://www.cnblogs.com/depth-perception/p/12600038.html