isprime_判断质数

判断质数的方法有很多，首先是最简单的试除法，判断n以内的质数的话时间复杂度为n*sqrt(n)当然是很慢的了

下面提供三种判断质数的方法：

首先是跑5051ms的这个是埃拉托斯特尼筛法且不加优化核心质数的倍数一定不是质数

#include<iostream>

#include<cmath>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#include<stack>

#include<string>

#include<cstring>

#include<map>

#include<vector>

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const long long maxn=;

long long n,m;

long long a[maxn];

void bwy()//闻道玉门犹被遮，应将性命逐轻车

{

    for(long long i=;i<=m;i++)a[i]=;

    a[]=;

    for(long long i=;i<=m;i++)

    {

        if(a[i]==)

        {

            for(long long j=i<<;j<=m;j+=i)

            {

                a[j]=;

            }

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    m=read();n=read();

    bwy();

    for(long long i=;i<=n;i++)

    {

        long long x;

        x=read();

        if(a[x]==)printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

从当前质数的1倍筛到n/i倍即可。

然后第二种是其优化算法也是竞赛之中使用最多的筛法。经观察发现可以从i*i筛到n/i;这样即可。

#include<iostream>

#include<string>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iomanip>

#include<ctime>

#include<vector>

#include<queue>

#include<map>

#include<stack>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m;

int a[];

void wy()

{

    a[]=;

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

    {

        if(a[i]==)

        {

            for(int j=i;j<=n/i;j++)

            {

                a[i*j]=;

            }

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    wy();

    for(int i=;i<=m;i++)

    {

        int x;

        x=read();

        if(a[x]==)printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

第三种则是真正的线性筛法了，埃拉筛法。找到每个数的最小质因子使筛出的数字只被唯一筛出~

#include<iostream>

#include<string>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iomanip>

#include<ctime>

#include<vector>

#include<queue>

#include<map>

#include<stack>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m;

int prime[],v[],top=;//v数组里存在i的最小质因子

void wy()

{

    memset(v,,sizeof(v));

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

    {

        if(v[i]==){v[i]=i;prime[++top]=i;}

        for(int j=;j<=top;j++)

        {

            if(prime[j]>v[i]||prime[j]>n/i)break;

            v[i*prime[j]]=prime[j];

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    wy();

    for(int i=;i<=m;i++)

    {

        int x;

        x=read();

        if(v[x]==x)printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

You're perfectly wrong for me.

巴特西

isprime_判断质数

最新文章

热门文章