【算法】素数筛

【算法】素数筛

Richard

2019 年 04 月 22 日

705 次浏览

暂无评论

1634字数

数据结构与算法

素数筛是我最早接触的几个算法之一。今天忽然发现有点不会写它了，于是重新温习一下。

引言

素数判断应该是刚开始的时候接触的比较多的一个(最少我写了一堆有关素数的题目)。素数的定义很简单：
只要一个数只有两个因子，1和它本身，那么这个数就是一个素数。
但如何验证一个数是素数呢？我第一个想到的是小于它的每个数都去除一遍。那么…………好吧我的废话有点多，下面列举三个方法吧。

1. 暴力循环

计算机擅长的是什么？循环嘛。那就让它循环吧：

/*****************************************************************
Function:暴力就完事了
Time complexities: O(N!)
*****************************************************************/

bool IsPrime(int n)
{
    if (n < 2)
        return false;

    for (int i = 2; i*i < n - 1; i++)
    {    //上面这里我小小的优化了一下，复杂度还没那么高
        if (n % i == 0)
            return false;
    }

    return true;
}

然后，再for循环逐个判断…………
再然后，一个大大的TLE摆在你面前。

2. 埃拉托斯特尼筛法

TLE总不能就不管了吧？我们来找古希腊数学家埃拉托斯特尼帮我们解决(其实这个名字我还是现场Google的，怎么记得住哦)。他提出了一种算法叫“埃拉托斯特尼筛法”。

原理：

这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。

所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。

简单来讲，素数的倍数一定不是素数。

代码实现

/*****************************************************************
Function:埃拉托斯特尼筛法
Time complexities: O(NloglogN)
*****************************************************************/

#include <algorithm>
using namespace std;

const int maxn = 65535;

bool prime[maxn];

void IsPrime()
{
    fill(prime, prime + maxn, true);
    //将所有重置为真
    prime[0] = prime[1] = 0;

    for (int i = 2; i < maxn; i++)
    {
        if (prime[i])
        {    //素数的倍数一定不是素数
            for (int j = i << 1; j < maxn; j += i)
                prime[j] = false;
        }
    }

    return;
}

详细步骤？自己去Wiki上看去。

3. 欧拉筛

什么？还是TLE？那就再精简一点吧。
我们发现，在埃，埃拉…………埃式素数筛中，有些数是被重复筛了。比如60，它首先被2筛了一遍，又被3筛了一遍，还要被5筛一遍。这样就浪费了很多时间。那怎么办呢？我们可以找欧拉筛。

思路

首先先明确一个条件：

任何合数都能表示成一系列素数的积

(别问我为什么，自己去验证)

然后，对于一个数 n ：

如果 n 是素数，那么它和比它小的素数的乘积一定不会被重复筛。
如果 n 是合数，此时 n 可以表示成递增素数相乘 n = p1 x p2 x …… x pn, 其中pi都是素数（2<=i<=n）， pi<=pj ( i<=j ) 。这时候我们只需要在p1的时候筛掉这个数就好了。

总结下来就是：对于每个合数，都只由它最小的质因子筛掉。

代码

/*****************************************************************
Function:线性素数筛
Time complexities: O(N)
*****************************************************************/

#include <algorithm>
using namespace std;

const int maxn = 65535;

bool check[maxn];
int prime[maxn];
int cnt = 0;

void IsPrime()
{
    fill(check, check + maxn, true);
    check[0] = check[1] = false;

    for (int i = 2; i < maxn; i++)
    {
        if (check[i])
            prime[cnt++] = i;

        for (int j = 0; j < cnt && i * prime[j] < maxn; j++)
        {
            check[i * prime[j]] = false;
            //判重。这一步是重点
            if (i % j == 0)
                break;
        }
    }

    return;
}

就先到这里吧，我要去补作业了(捂脸)。还有一堆资料没整理呢…………

【算法】素数筛