C++如何实现素数判断 |21xrx.com

C++如何实现素数判断

2023-06-24 00:52:23 深夜i -- --

C++ 素数实现判断

素数，即只能被1和它本身整除的正整数，是数学中一个重要的概念。在计算机领域中，判断一个数是否为素数常常用到，因此C++中实现素数判断也成了必须学会的基础知识。

C++中实现素数判断的方法有很多，下面介绍两种常用的方法。

方法一：暴力枚举法

该方法即遍历该数的所有可能因子，判断是否有除1和它本身外能整除它的数。代码如下：


#include <iostream>
#include <cmath>
bool is_prime(int n){
  if(n<=1) return false; //若n<1，则一定不是素数
  int m = sqrt(n)+1;
  for(int i=2;i<m;i++)
    if(n%i==0) return false;
  return true;
}
int main(){
  int n;
  std::cin >> n;
  if(is_prime(n)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
  return 0;
}

该代码首先判断n是否小于等于1，若是则直接返回false。然后通过求n的平方根+1的方式得到遍历的上界，因为如果n有一个大于sqrt(n)的因子，则它必定有一个小于sqrt(n)的因子。然后从2开始遍历到上界，判断n是否能被遍历到的数整除，若是，则返回false，表明该数不是素数。若遍历完毕都没有找到能整除n的数，则返回true，表明该数是素数。

该方法的时间复杂度为O(sqrt(n)),相对较慢，不适用于大数判断。

方法二：快速素数判断法

该方法则是通过一个重要的定理--费马小定理来实现。费马小定理在数论中颇为重要，它指出对于任何质数p和任意整数a，a的p次方除以p的余数等于a除以p的余数的p次方除以p的余数。即a^p ≡ a (mod p)。因此，若 n 是一个质数，a 是不在n倍数集合中的整数，则a的n-1次方除以n的余数一定是1。根据这个定理，可以设计出快速素数判断法。代码如下：


#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
LL quick_pow(LL a,LL b,LL mod){
  LL res =1;
  while(b){
    if(b&1) res=(res*a)%mod;
    a=(a*a)%mod;
    b=b>>1;
  }
  return res;
}
bool miller_rabin(LL n){  //用于检测n是否是合数，是则返回false
  if(n<2||n==4) return false;
  if(n==2||n==3) return true;
  LL s=n-1;
  while(s%2==0)
    s>>=1;
  
  for(int i=0;i<8;i++){ //取a=2,3,5,7,11,13,17,19这几个数进行检测
    LL a= rand()%(n-2)+2;
    LL temp = s;
    LL mod = quick_pow(a,temp,n);
    while(temp!=n-1&&mod!=1&&mod!=n-1){
      mod = (mod*mod)%n;
      temp<<=1;
    }
    if(mod!=n-1&&(temp&1)==0) return false;
  }
  return true;
}
bool is_prime(LL n){
  if(n<=1) return false;
  if(n<=1000000){  //对于较小的数，调用暴力枚举法
    for(LL i=2;i<n;i++){
      if(n%i==0) return false;
    }
    return true;
  }
  else{ //否则调用Miller-Rabin算法判断
    return miller_rabin(n);
  }
}
int main(){
  LL n;
  std::cin >> n;
  if(is_prime(n)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
  return 0;
}

该代码中，首先定义了两个函数：quick_pow(a,b,mod)用于求a的b次方除以mod的余数（避免爆long long），miller_rabin(n)用于检测n是否是一个合数。再定义is_prime(n)函数，其中当n较小时，调用暴力枚举法进行判断，当n较大时，调用miller_rabin(n)进行素数判断。在miller_rabin(n)函数中，先对特殊情况（n小于2或4）进行判断，然后计算n-1的奇数因子s，再取a=2,3,5,7,11,13,17,19进行检测。若检测到a的temp次方除以n的余数不为1或n-1，则不是素数，返回false。若遍历所有取值均为素数，则该数可能是素数，返回true。若经过8轮检测还不能判断出n是否是素数，则很可能是素数，返回true。该方法的时间复杂度为O(log2(n)log3(n))，比暴力枚举法更加高效。

总结：

由以上介绍，我们了解了在C++中实现素数判断的两种常用方法。当判断的数较小时，采用暴力枚举法开销会较小，判断速度较快；而当判断的数较大时，采用快速素数判断法可以大大缩短判断时间，提高算法效率。

上一篇: idea打包java可执行jar包

下一篇: C++并发库：提高多线程程序的效率

评论区

()

相似文章