算法学习-数论专题-素数的判定

版权声明：本篇文章由特邀讲师胡家睿撰写，tth37只负责搬运、整理和发布；版权归胡家睿所有。

概述

素数定义：除1和本身以外没有其他因数的数

素数在信息学竞赛中有较多的应用，素数判定是解决复杂数论问题的基础。本篇文章介绍了一些素数判定的方法。

单个素数判定

朴素判定：

bool prime(int n){
    if(n==1) return false;//特判1（不为素数）
    for(int i=2;i<n;++i){
        if(n%i==0) return false;//除1、n以外还存在因数，所以n为合数；
    }
    return true；//循环后没有判定为合数，则为素数。
}

时间复杂度：$\Theta (n)$

优化：

bool prime(int n){
    if(n==1) return false;//特判1（不为素数）
    for(int i=2;i<=sqrt(n);++i){
        if(n%i==0) return false;
    }
    return true；
}

时间复杂度：$\Theta(\sqrt{n})$

证明：

若一个数$n$为合数，则它一定拥有一个质因数$k$。可以知道，$n/k$（记为$s$）为$n$的因数，且$s$不等于$n$。$k$和$s$二者必定有一个数小于等于$\sqrt{n}$，否则$k*s$一定大于$n$。所以只要在$\sqrt{n}$以内循环一遍即可。

埃氏素数筛

如果用上面的方法判定$1-n$以内所有素数，会发现时间复杂度非常高。那么这个时候就要用筛法了。大致意思是用素数来筛掉合数，然后用$f$数组储存是否是素数。

f[1]=true;//特判还是很必要的
for(int i=2;i<=n;++i){
    if(f[i]) continue;//i为合数直接跳过
    for(int j=i+i;j<=n;j+=i){
        f[j]=true;//i为素数，i的倍数一定为合数
    }
}

优化：

f[1]=true;
for(int i=2;i<=n;++i){
    if(f[i]) continue;
    for(int j=i*i;j<=n;j+=i){//这里只变了乘号，但是会快很多喔
        f[j]=true;
    }
}

原因是：$i*i$以下的所有合数都已经被筛掉了。具体证法，可以接着看下去（在线性筛里有类似的思想，所以看完可以尝试一下自己证明）。

素数线性筛

上一个筛法时间复杂度$\Theta(log log n)$非常接近线性。但是要达到线性还差一点（这里不是比赛要求掌握所以就当兴趣学吧）

上一个筛法的大概想法，是每一个素数的倍数都筛掉，所以是让每一个合数都被它的质因子筛一遍。

那么接下来的筛法，就是让每个合数的最小质因子筛一遍（要开一个prime数组存所有素数）。先放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[10005],prime[10005];
int main()
{
    ll n,i,j,cnt=0;
    cin>>n;
    //这个地方不用特判1,因为我们判定是否为素数的方法是f[i]是否为0; 
    for(i=2;i<=n;++i)
    {
        if(!f[i]) 
        {
            prime[++cnt]=i;//存入素数; 
            f[i]=i;
        }
        for(j=1;j<=cnt;++j)
        {
            if(prime[j]*i>n||prime[j]>f[i]) break;//判定出界或i的因子中有比当前素数更小的（即prime[j]*i已经被f[i]筛过了）; 
            f[prime[j]*i]=prime[j];//标记所有未被标记的i的倍数； 
        }
    }
    cin>>i;
    cout<<f[i]<<" ";
    return 0;
 }

核心就在于神奇的判定方法，可以多咀嚼咀嚼

时间复杂度$\Theta(n)$搞定，还可以找到$1-n$内所有合数的最小质因数。

# 数学, 素数

算法学习-数论专题-素数的判定

概述

单个素数判定

埃氏素数筛

素数线性筛

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!