C++语言中的素数判断方法 |21xrx.com

C++语言中的素数判断方法

2023-07-01 18:03:23 深夜i -- --

C++ 素数判断方法

素数是指只能被1和本身整除的数，如2、3、5、7等。在C++语言中，判断一个数是否为素数可以用以下方法。

1. 常规方法

常规方法是从2开始，逐一判断该数是否能够被整除，如果能被整除则不是素数，如果一直到该数的平方根还没有被整除，则该数为素数。代码如下：


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. 埃氏筛法

埃氏筛法是一种比常规方法更快的判断素数的方法。它的思想是用一个数组来记录每个数是否为素数，如果是素数，则将它所有的倍数都标记成非素数。具体实现代码如下：


bool isPrime(int n) {
  if (n <= 1) return false;
  bool *is_prime = new bool[n + 1];
  memset(is_prime, true, sizeof(bool) * (n+1));
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i <= sqrt(n); i++) {
    if (is_prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  bool ret = is_prime[n];
  delete[] is_prime;
  return ret;
}

3. 米勒-拉宾素性检验

米勒-拉宾素性检验是一种著名的判断素数的方法，它的原理是假设n是素数，那么对n-1进行因式分解，得到n-1=q*(2^k)，其中q是奇数，k是正整数。然后随机选择一个小于n的数a，计算a^q(mod n)，如果等于1或者等于n-1，则认为n是素数，否则继续计算a^(2q), a^(4q)...直到计算到a^(2^(k-1)*q)。具体实现代码如下：


int pow_mod(int a, int b, int m) {
  int ans = 1;
  while (b > 0) {
    if (b & 1) ans = (ans * a) %m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ans;
}
bool miller_rabin(int n) {
  if (n <= 1) return false;
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0) return false;
  int k = 0, q = n - 1;
  while (q % 2 == 0) {
    k++;
    q >>= 1;
  }
  for (int i = 0; i < 5; i++) {
    int a = rand() % (n - 3) + 2;
    int x = pow_mod(a, q, n);
    if (x == 1 || x == n - 1) continue;
    for (int j = 1; j < k; j++) {
      x = (x * x) % n;
      if (x == n - 1) break;
    }
    if (x != n - 1) return false;
  }
  return true;
}

以上是几种常见的判断素数的方法，它们各自有着不同的适用场景和优劣点。在实际编程中需要根据具体情况选择适当的方法。

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

下一篇: C++实数输出宽度的默认最大值是多少？

评论区

()

相似文章