求一个数是否为素数
剑枫 / 2020-03-27 / 默认分类 / 阅读量 57

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

一、普通求法

  思路:用循环来求,从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;}