MENU

Catalog

    求一个数是否为素数

    March 27, 2020 • Read: 76 • c/c++基本算法

    求一个数是否为素数有很多求解方法下面列出几个供参考

    一、普通求法

      思路:用循环来求,从2开始循环一直到根号n。

       为什么只需要判断到根号n?
    
    因为n=√n*√n,n的因数除了√n,其他都是成对存在的,且必定一个大于√n一个小于√n,
    

    假设n不是质数,有个因数大于√n(不是n本身),则n必定有一个与之对应的小于√n的因数。这个比较简单。

    时间复杂度为O(n)。

    #include<bits/stdc++.h>
    using namespace std;
    int sushu(int n)
    {
      if(n==1) return 0;
      int k;
      k=sqrt(n);
      for(int i=2;i<=k;i++)
      {
        if(n%i==0) return 0;
      }
      return 1;
    }
    int main()
    {
      int n;
      while(cin>>n)
      {
        int l=sushu(n);
        if(l) printf("ture\n");
        else
        {
          printf("no\n");
        }
      }
      return 0;
    
    }
    

    二、用素数筛来判断。(这个可能有点大材小用了,但对于大的数据还是可以的)

     素数筛可以分为埃及筛和线性筛。
    

     1、埃及筛。

      和数的倍数一定会在筛素数倍数的时候被筛掉,所以只筛素数就好,只把质数的素数筛掉。就是找到一个质数,把他的倍数全部标记为合数。但是你会发现有的数字会被标记多次,比如12被2,3都标记,但是这样会浪费时间。(一般的话,如果数据是1e9的话,用这个就行了,时间复杂度是nloglogn)。

         下面给出模板:
    const int N=1e7+1;
    int prime[N];//打表,将素数弄成表格,就是将范围内的所有素数记录下来
    int b[N];//相当于桶排序,将原先已经记录的素数标记,然后在后来的筛选中跳过就行了。
    int cnt=0,max1=1e7;
    int init()
    {
        memset(b,1,sizeof(b));//将b[N]数组全部初始化为1;
        b[0]=b[1]=0;
        for(int i=2;i<=max1;i++)//开始找素数。
        {
            if(b[i])    //将第一次出现的素数标记,因为后面要将此数的倍数标记了,然后再次遇到次数的倍数是直接跳过
            {
                prime[++cnt]=i;         //进行打表
    
                for(int j=2;j*i<=max1;j++)//标记此数(i)的倍数
                {
                    b[i*j]=0;
                }
            }
        }
        return 0;
    }
    

    一般来说用埃及筛就够了。

    2、线性筛

    素数筛可以优化,普通的线性筛法虽然大大缩短了求素数的时间,但是实际上还是做了许多重复的运算,比如2*3=6,在素数2的时候筛了一遍,在素数3的时候又筛了一遍。如果只筛小于等于素数i的素数与i的乘积,既不会造成重复筛选,又不会遗漏。时间复杂度几乎是线性的。(线性筛可以筛选范围在2e9的素数)

      上代码:

    const int N=1e7+1;
    int prime[N];
    int b[N];
    int cnt=0,max1=1e7;
    int init()
    {
        memset(b,1,sizeof(b));
        b[0]=b[1]=0;
        for(int i=2;i<=max1;i++)
        {
            if(b[i])
            prime[++cnt]=i;
            for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
            {
                b[prime[j]*i]=0;
                if(i%prime[j]==0) break;
            }
    
        }
        return 0;
    }
    

    我们要筛1~n中的素数,然后先默认他们都是素数,最外层枚举
    1~n的所有数,
    如果它是素数,就加到素数表,
    对于每一个枚举的i ,枚举素数表里的数,然后素数就会标记自己 i
    倍的数不是素数,(素数的倍数不是素数)
    枚举素数表什么时候停?枚举到i的最小质因子,标记完就可以停
    了,保证每个数只被他的最小质因子筛掉。
    例如:外层i=15时,素数表里:2,3,5,7,11,13
    215=30,把30筛掉;315=45,把45筛掉,因为15%3==0,退
    出里面的循环;
    15是被3筛掉的,因为3是15的最小素因子。

    3、知道了埃及筛和线性筛,接下来就要上主菜——如何判断素数了。

    sqrt 判别 O (√N) )
    如果x可以表示为两个因子相乘
    x=a*b 假设a<=b
    那么x>=a*a
    a<=√x
    只需要枚举a<=√x就可以了

    int sushu(long long n)
    {
        int flag=0;
        for(int i=1;prime[i]<sqtr(n);i++)
        {
            if(n%prime[i]==0) {flag=1;break;}
        }
        if(n==1) flag=1;
        return flag;
    }
    

    然后主函数里一定要写init();才能调用成功。

    举个例子:

    知否知否,应是绿肥红瘦
    Problem:1704
    Time Limit:1000ms
    Memory Limit:165535K
    Description
    宋朝的女子嫁人时,要考察男子的满意度(满意度=财富值+地位值-婆婆的暴力值)
    如果满意度是素数的话,就可以嫁,否则就不答应这门婚事。
    Input
    第一行是n(1<=n<=50),表示数据的组数;
    接下来是n行,每行3个正整数x,y,z(财富值,地位值,暴力值);(1<=x,y,z<=1e14)
    Output
    如果可以同意这门婚事,输出"yes";
    否则输出"no";
    Sample Input
    2
    10 2 1
    10 2 2
    Sample Output
    yes
    no
    ——————————————————————————————————————————————————————
    这就是典型的素数筛
    素数筛就行,因为是1e14,所以筛到1e7就行!

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=1e7+1;
    int prime[N];int b[N];
    int cnt=0,max1=1e7;
    int init(){
        memset(b,1,sizeof(b));
        b[0]=b[1]=0;
        for(int i=2;i<=max1;i++)
        {
            if (b[i])
            prime[++cnt]=i;
             //for(int j=2;j*i<=1000;j++)
              //b[i*j]=0;
     
             for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
                {
                    b[prime[j]*i]=0;
                    if (i%prime[j]==0) break;
                }
     
     
     
        }
     
        return 0;}
    int su(LL n){
        int flag=0;
        for(int i=1;prime[i]<=sqrt(n*1.0);i++)
        if (n%prime[i]==0) {flag=1;break;}
        if (n==1) flag=1;
        return flag;}<br>int main(){
        int n;
        LL x,y,z;
        init();
        cin>>n;
        while(n--)
        {
          cin>>x>>y>>z;
          if (su(x+y-z)==0) cout<<"yes"<<endl;
          else
                cout<<"no"<<endl;
     
     
     
        }
     
     
        return 0;}
     
    Last Modified: September 21, 2020