21xrx.com
2024-12-22 21:40:33 Sunday
登录
文章检索 我的文章 写文章
C++中如何表示素数
2023-07-11 21:01:58 深夜i     --     --
C++ prime numbers representation

在计算机科学中,素数是一个非常重要的概念,因为它们被广泛应用于密码学、算法和其他计算机科学领域中。在C++中,表示素数有几种不同的方法。本文将详细介绍这些方法。

方法1:暴力检查法

暴力检查法是最基本的素数检查方法。其思路是从2开始到该数的根号下止,遍历所有可能的因子,如果存在一个因子可以整除该数,则该数不是素数,否则它是素数。

以下是使用C++代码实现的暴力检查法:

bool isPrime(int n){

  if(n<=1) return false;

  for(int i=2;i<=sqrt(n);i++){

    if(n%i==0) return false;

  }

  return true;

}

方法2:质数筛选法

质数筛选法是一种更快速的素数判断方法,其思路是将不是素数的数从候选列表中排除,只保留素数。使用埃拉托色尼筛法实现,先将2到n的整数存储在数组中,从2开始往上枚举,若当前数已经被排除则跳过,否则将该数的倍数全部排除,直到它的平方大于n。

以下是使用C++代码实现的质数筛选法:

vector primes(int n){

  vector isPrime(n+1,true);

  vector res;

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

    if(isPrime[i]){

      res.push_back(i);

      for(int j=2*i;j<=n;j+=i){

        isPrime[j]=false;

      }

    }

  }

  return res;

}

方法3:米勒-拉宾测试法

米勒-拉宾测试法是一种更强大的素数检验方法,可以在常数时间内确定一个数是否是素数。它的基本思路是:对于一个奇素数n,设n-1=2^s*t,其中t是奇数,选取一个a∈[2,n-1],计算a^t mod n和a^(2^k*t) mod n(0<=k<=s-1),若结果不为1且不为n-1,则n不是素数,反之n可能是素数。

以下是使用C++代码实现的米勒-拉宾测试法:

long long qmul(long long a,long long b,long long m){

  long long res=0;

  while(b){

    if(b&1) res=(res+a)%m;

    a=(a+a)%m;

    b>>=1;

  }

  return res;

}

long long qpow(long long a,long long b,long long m){

  long long res=1;

  while(b){

    if(b&1) res=qmul(res,a,m);

    a=qmul(a,a,m);

    b>>=1;

  }

  return res;

}

bool Miller_Rabin(long long n){

  if(n<=2) return n==2;

  long long s=0,t=n-1;

  while((t&1)==0){

    t>>=1;

    s++;

  }

  for(int k=0;k<8;k++){

    long long a=rand()%(n-2)+2;

    long long x=qpow(a,t,n);

    for(int i=0;i

      long long nxt=qmul(x,x,n);

      if(nxt==1&&x!=1&&x!=n-1) return false;

      x=nxt;

    }

    if(x!=1) return false;

  }

  return true;

}

总结:

以上是三种在C++中表示素数的方法,暴力检查法适用于小规模的数,,质数筛选法则适用于大批量素数的处理,而米勒-拉宾测试法则更加高效和准确。因此在实际应用中需要根据具体问题选择合适的方法。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复