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

C++程序中如何判断素数

2023-07-05 12:44:56 深夜i -- --

C++ 素数判断

在C++编程中，判断一个数是否为素数是一种基本的算法问题。素数，也称质数，指大于1的自然数，除了1和它本身以外不再有其他因数的自然数。下面介绍两种简单的方法来判断一个数是否为素数。

方法一：暴力枚举法。

暴力枚举法是一种最基本的判断素数的方法。该方法的原理是：遍历2到sqrt(n)之间的所有自然数，如果n可以被其中任何一个数整除，则n不是素数，否则n是素数。这是因为，如果一个数n可以被分解成两个自然数a和b的乘积（a * b = n），其中a和b均小于sqrt(n)，那么a和b中必定有一个小于等于sqrt(n)。因此，只需遍历2到sqrt(n)之间的所有自然数即可。

下面是暴力枚举法的C++代码：


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

方法二：Miller-Rabin算法。

Miller-Rabin算法是一种高效的素数测试算法，也是一种随机算法。该算法的基本思想是利用模幂运算进行判断。具体方法是，将待判断的数n写成2^k * q + 1的形式，其中k为非负整数，q为奇数。接着，随机选取一个整数a，计算a^q mod n的值。若该值为1或者n-1，则n有可能为素数，需要进行下一轮测试。否则，重复平方操作，计算a^(2q) mod n, a^(4q) mod n, ..., 直到计算出a^(n-1) mod n。如果其中出现了1和n-1之外的其它值，那么n不是素数。如果执行了t轮测试，对于任意的合数n，至少有3/4的测试都能检测出来。具体的t值可以通过计算得到，一般取t=10即可。

下面是Miller-Rabin算法的C++代码：


int random(int l, int r) {
  return rand() % (r - l + 1) + l;
}
int powMod(int a, int b, int m) {
  int res = 1 % m;
  for (; b; b >>= 1) {
    if (b & 1) res = 1ll * res * a % m;
    a = 1ll * a * a % m;
  }
  return res;
}
bool MillerRabin(int n) {
  if (n < 2) return false;
  int s = n - 1;
  while (!(s & 1)) s >>= 1;
  for (int i = 0; i < 10; i++) {
    int a = random(1, n - 1);
    int t = s;
    int m = powMod(a, t, n);
    while (t != n - 1 && m != 1 && m != n - 1) {
      m = 1ll * m * m % n;
      t <<= 1;
    }
    if (m != n - 1 && !(t & 1)) return false;
  }
  return true;
}

总结

判断素数是一种经典的算法问题，在C++编程中有多种方法可以实现。如果需要判断的数比较小，可以选择暴力枚举法，其时间复杂度为O(sqrt(n))。如果需要判断的数比较大，可以采用Miller-Rabin算法，其时间复杂度为O(k * log^3(n))，其中k为测试次数。

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

下一篇: C++如何读取HTML文件

评论区

()

相似文章