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

C++中如何判断素数

2023-06-22 03:43:36 深夜i 12 0

C++ 素数判断

素数指的是只能被1和自身整除的自然数。在使用C++编程时，判断一个数是否为素数是非常常见的操作。本文将介绍C++中判断素数的几种方法。

方法一：暴力枚举

暴力枚举是最简单的判断素数的方法。即从2开始一直枚举到该数的开方，如果该数能被其中任意一个数整除，则该数不是素数。

具体实现代码如下：

bool isPrime(int num) {
  if (num <= 1) return false; // 小于等于1的不是素数
  for (int i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) return false;
  }
  return true;
}

该方法的时间复杂度为O(sqrt(n))，在数据较小的情况下可行，但是在数据很大的情况下会比较耗时。

方法二：Sieve of Eratosthenes

埃氏筛法是一种比较高效的判断素数的方法，可以减少无用的计算时间。具体思路是从2开始，每次选取一个质数，筛掉能被该质数整除的所有数，重复该操作直到筛选完所需的范围。

实现代码如下：

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

该方法的时间复杂度为O(nloglogn)，比暴力枚举要快，但是需要使用额外的空间。

方法三：米勒-拉宾素数判定法

米勒-拉宾素数判定法是一种基于费马小定理的判断素数的方法。具体是选择一个随机数，判断该随机数是否符合费马小定理，重复该操作k次，如果k次都符合，则该数很有可能是素数。

实现代码如下：

long long mul_mod(long long a, long long b, long long mod) {
  long long ans = 0, base = a % mod;
  while (b) {
    if (b & 1) ans = (ans + base) % mod;
    base = (base << 1) % mod;
    b >>= 1;
  }
  return ans;
}
long long pow_mod(long long a, long long b, long long mod) {
  long long ans = 1, base = a % mod;
  while (b) {
    if (b & 1) ans = mul_mod(ans, base, mod);
    base = mul_mod(base, base, mod);
    b >>= 1;
  }
  return ans;
}
bool Miller_Rabin(long long n) {
  if (n < 2) return false;
  if (n != 2 && n % 2 == 0) return false;
  int s = 0;
  long long d = n - 1;
  while (d % 2 == 0) {
    s++;
    d >>= 1;
  }
  for (int i = 0; i < 8; i++) {
    long long a = rand() % (n - 1) + 1;
    long long x = pow_mod(a, d, n);
    long long y = 0;
    for (int j = 0; j < s; j++) {
      y = mul_mod(x, x, n);
      if (y == 1 && x != 1 && x != n - 1)
        return false;
      
      x = y;
    }
    if (y != 1)
      return false;
    
  }
  return true;
}
bool isPrime(int num) {
  return Miller_Rabin(num);
}

该方法的时间复杂度为O(klogn)，其中k为重复次数，需要注意的是，该方法只是概率性判断，可能会判定错误。

综上所述，C++中判断素数的方法不止于以上三种，具体选择哪种方法取决于数据范围和精度要求。

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

下一篇: C++如何调用父类的方法？

评论区

相似文章