数论：筛质数

mydcwfy · 2021-06-29 21:34:32 · 个人记录

筛质数

1. 埃氏筛法

比较简单，算法核心就是直接将所有该质数的所有倍数筛掉。

for (int i=2;i<=n;++i)
{
    if (isprime[i]) prime[cnt++]=i;
    else break;
    for (int j=2*i;j<=n;j+=i)
            isprime[j]=false;
}

时间复杂度为 O(n*(1/2+1/3+...))=O(n \log \log n)。

2. 线性筛法

先看代码。

for (int i=2;i<=n;++i)
{
    if (isprime[i]) prime[cnt++]=i;
    for (int j=0;j<cnt&&i*prime[j]<=n;++j)
    {
        isprime[i*prime[j]]=false;
        if (i%prime[j]==0) break;
    }
}

可以证明，每一个合数都只会被它的最小质因数筛掉。

时间复杂度为 O(n)。

3. 例题

T1：哥德巴赫猜想

题目传送门 Luogu

直接枚举所有质数，看减后的数是不是素数即可。

代码略。

T2：Sherlock and his girlfriend

题目传送门 Luogu(RemoteJudge:Codeforces)

可以发现，该限制条件是质数与合数之间，不可能是质数与质数之间，合数与合数之间。

所以该图为二分图（按限制条件建边），答案不超过二。

只要有合数，那么答案必然为 2。

即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int prime[N],cnt;
bool isprime[N];

void init()
{
    for (int i=2;i<N;++i) isprime[i]=true;
    for (int i=2;i<N;++i)
    {
        if (isprime[i]) prime[cnt++]=i; 
        for (int j=0;j<cnt&&i*prime[j]<N;++j)
        {
            isprime[i*prime[j]]=false;
            if (!(i%prime[j])) break;
        }
    }
    return ;
}

int main()
{
    init();
    int n;cin>>n;
    if (n>=3) puts("2");
    else puts("1");
    for (int i=1;i<=n;++i)
        if (isprime[i+1]) printf("1 ");
        else printf("2 ");
    return 0;
}

T3：质数距离

题目传送门 AcWing

这道题，需要我们去改进该算法。

因为所有算法都是从 1 开始的，且至少要 O(n)。

仔细分析，我们发现，任何一个数，都有一个质数 \leq \sqrt n。

所以，我们可以先处理出所有 \leq \sqrt n 的质数，然后用这些数去筛 [L,R]。

复杂度为 O((R-L)\log\log R)。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define mp make_pair
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<long long,long long> PLL;
const int N=50000,T=1e6+10,INF=1e9;
int prime[N],cnt;
bool isprime[N];
bool vis[T];
ll l,r;

void init()
{
    memset(isprime,true,sizeof isprime);
    for (int i=2;i<N;++i)
    {
        if (isprime[i]) prime[cnt++]=i;
        for (int j=0;j<cnt&&prime[j]*i<N;++j)
        {
            isprime[i*prime[j]]=false;
            if (!(i%prime[j])) break;
        }
    }
}

int main()
{
    init();
    while (cin>>l>>r)
    {
        memset(vis,0,sizeof vis);
        for (int i=0;i<cnt;++i)
        {
            ll p=prime[i],low=(l+p-1)/p,high=r/p;
            for (int j=max((ll)2,low);j<=high;++j)
                vis[p*j-l]=true;
        }
        ll maxn=0,minx=INF;
        PLL maxp,minp;
        for (int i=0,last=-1;i<=r-l;++i)
            if (!vis[i]&&i+l>=2)
            {
                if (~last)
                {
                    if (maxn<i-last) maxn=i-last,maxp=mp(last+l,i+l);
                    if (minx>i-last) minx=i-last,minp=mp(last+l,i+l);
                }
                last=i;
            }
        if (maxn==0) puts("There are no adjacent primes.");
        else printf("%lld,%lld are closest, %lld,%lld are most distant.\n"
            ,minp.x,minp.y,maxp.x,maxp.y);
    }
}

T4：阶乘分解

题目传送门 AcWing

将所有的质数的次数存下来即可。