C++实现素数判断的多种方法 |21xrx.com

C++实现素数判断的多种方法

2023-07-01 07:40:05 深夜i 14 0

C++ 素数判断方法实现多种

素数是指只能被1和本身整除的整数。在计算机编程中，判断一个数是否为素数是非常常见的需求。C++作为一门流行的编程语言，有很多种实现素数判断的方法。本文将介绍一些常用的方法。

1. 埃拉托色尼筛法

埃拉托色尼筛法，也叫筛法求素数，是一种比较高效的素数判断方法。其基本思想是从2开始，将每个素数的倍数都标记成合数，直到筛完所有小于等于给定数的数。最后留下的未被标记的数即为素数。代码实现如下：

bool isPrime(int n){
  if(n<2) return false;
  vector<bool> prime(n+1,true);
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i*i<=n;++i){
    if(prime[i]){
      for(int j=i*i;j<=n;j+=i){
        prime[j] = false;
      }
    }
  }
  return prime[n];
}

2.暴力枚举法

暴力枚举法，也叫试除法，是一种比较简单但效率较低的判断素数的方法。其基本思想是从2开始，依次将该数除以2到该数的平方根的每个整数，如果均不能整除，则该数为素数。代码实现如下：

bool isPrime(int n){
  if(n<2) return false;
  for(int i=2;i<=sqrt(n);++i){
    if(n%i==0) return false;
  }
  return true;
}

3.费马小定理

费马小定理是数论中很重要的一个定理，它可以用来判断素数。其基本思想是对任意质数P，对任意整数a，a的P次方减去a一定是P的倍数。因此，如果N不是质数，则对于任意小于N的a，a的N-1次方减去1一定是N的倍数。代码实现如下：

bool isPrime(int n){
  if(n<2) return false;
  for(int i=2;i*i<=n;++i){
    if(n%i==0) return false;
  }
  return true;
}

4.米勒-拉宾素性检验法

米勒-拉宾素性检验法是一种相对较为复杂但效率较高的判断素数的方法。其基本思想是通过对N-1进行分解，将N-1表示为2^r*d的形式，然后随机选择一个整数a，计算a^d mod N是否等于1，或等于N-1。若等于1则N可能为质数，若等于N-1则继续下一轮测试。重复测试k次，若均为可能则是素数。代码实现如下：

long long power(long long a,long long b,long long mod){
  long long ans = 1;
  while(b){
    if(b%2==1) ans = ans*a%mod;
    a = a*a%mod;
    b/=2;
  }
  return ans;
}
bool Miller_Rabin(long long n){
  if(n<2) return false;
  if(n==2||n==3||n==5) return true;
  if(n%2==0) return false;
  long long d = n-1,r = 0,a;
  while(d%2==0){r++,d/=2;}
  for(int i=1;i<=10;++i){ //测试10轮
    a = rand()%(n-4)+2;
    long long x = power(a,d,n);
    if(x==1||x==n-1) continue;
    for(int j=1;j<=r-1;++j){
      x = x*x%n;
      if(x==n-1) break;
    }
    if(x!=n-1) return false;
  }
  return true;
}

综上所述，C++实现素数判断的方法有很多，每种方法都有其应用的场景。在实际开发中，应根据需要选用最合适的方法来进行实现。

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

下一篇: C++中间件是什么？

评论区

相似文章