MENU

素数筛

April 4, 2020 • Read: 538 • 算法

》》2020.4.1修订版

自古以来,素数就是一个有众多人研究的东西,而素数筛也是这些研究成果中的一个

素数筛是用来快速生成一个素数表的东西,比起生成素数的幼稚算法及其优化的方法,素数筛的速度更快,但是也常常会出现很多奇奇怪怪的bug,以后再说。

今天先介绍一下欧拉筛埃氏筛

这两种筛法是素数筛里最常见的

1.埃氏筛

原理:

​ 素数的倍数一定不是素数

思路:

​ 我们先生成一个数组vis,给上面每一个位置都初始化为✔,然后将0和1位置变为✘,因为0和1一定不是素数

012345678910

​ 然后我们从第二格开始,因为2是素数,所以我们把4,6,8,10……都变为✘,如下表:

012345678910

​ 同样的,我们来看看第三个,因为3是素数,所以我们把6,9,12……都变为✘,如下表:

012345678910

​ 然后我们再来看看第四格,第四格已经被标记为了✘,所以我们跳过第四格,经过多次这样操作后,vis数组中便筛出了某一个范围内的所有素数

​ 我们再通过一次for循环遍历,找出所有标记为✔的下标,便是所求素数了

实现代码:

​ 实现代码可能和以上描述有些许出入,但是大体思路没有问题 : )

const int N=1e7+1;
int prime[N],cnt=0;
//prime存储的是素数表
bool vis[N];
//如果vis[n]的值为true,则该数为素数
//使用bool型,节省空间;
void get_prime(){
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=0;
    for (int i=2;i<N;i++){
        if (vis[i]){
            prime[++cnt]=i;
            for (int j=2;j*i<N;j++)
                vis[i*j]=false;
        }
    }
}

​ 该算法的时间复杂度为O(nlglgn)≈O(n),是一种趋近与线性的算法,速度较快,能够应付大多树的题目,那有没有更快的呢?

当然有!下面让我来介绍一个更快的算法:

2.欧拉筛(线性筛)

​ 在讲欧拉筛的时候,我们先回顾一下埃氏筛

​ 埃氏筛会对素数的所有倍数进行标记,这也导致了一个比较大的问题,例如:6,因为他是3的倍数,同时也是2的倍数,所以在埃氏筛中,6被删掉了两次,而在比较大的合数中,更是被删掉了更多次(每有一个素因子就会被删掉一次),这也导致了太多系统资源的浪费,同时也导致了时间的延长,更有可能会让程序的运算时间+1s,这是很危险的,所以我们要想办法来解决这个问题。

然后,欧拉筛诞生了。

原理

​ 任意一个合数都能由几个素数乘得

思路:

​ 我们先生成一个数组vis,给上面每一个位置都初始化为✔,然后将0和1位置变为✘,因为0和1一定不是素数

012345678910

​ 接下来,我们来看看2,这次,我不再将4,6,8,10……标记为✘了,我只将4标记为✘(4=2x2)

012345678910

​ 然后我们再来分析3,与上一步相同,我将6和9标记为✘(6=3x2,9=3x3)

012345678910

​ 然后再来看看4,尽管4已经被标记为了✘。我们将8,12标记为✘(8=4x2,12=4x3)

012345678910

​ 接下来看5,我们将10,15标记为✘……

​ 通过观察,我们发现,被标记的位置都是当前位置的数和该位置之前的素数的乘积,而每一个位置都只被标记了一次,节省了系统资源,时间-1s

代码实现:

const long long MAX=1e4+1;
int prime[MAX],cnt=0;
bool vis[MAX];
//vis[n]为true时,n为素数
int getprime(){
    memset(vis,1,sizeof(vis));
    vis[0]=vis[1]=0;
    for (int i=2;i<=MAX-1;i++){
        if (vis[i])
            prime[++cnt]=i;
        for (int j=1;j<=cnt&&prime[j]*i<=MAX-1;j++){
            vis[prime[j]*i]=0;
            if (i%prime[j]==0) break;
        }
    }
    return 0;
}

该算法比埃氏筛速度更快,但是一般的题目中,都推荐直接使用埃氏筛


番外个体:素数的判断

判断素数?这么简单的东西,刚刚学C++新手都会,这还用教?

是的,判断素数的幼稚算法确实简单,但是因为其时间复杂度实在太高O(n^2),在面对1e6这种数量级的数字时便显得软弱无力了,那么这种大数字的素数该如何判断呢?

当然是要结合素数筛法幼稚算法

首先,我们利用素数筛法筛出一定数量的素数,例如我们判断1e6这种怪物的时候,就生成1e3大小的素数集合prime,接下来要做的事,就是开始枚举,但是枚举也是有技巧的

我们只需要看这个数是不是素数的倍数,便可以知道这个数是不是素数

代码如下:

int isprime(int number){
    bool flag=false;
    for (int i=1;i<=sqrt(n);i++)
        if (number%prime[i]==0){
            flag=true;
            break;
        }
    if (n==1) flag=1;//对1进行特判
    return flag;
}
Archives Tip
QR Code for this page
Tipping QR Code