21xrx.com
2025-03-28 02:30:06 Friday
文章检索 我的文章 写文章
C++判断素数的方法
2023-07-05 08:19:49 深夜i     16     0
C++ 判断素数 方法 算法 质数

素数，即只能被1和自己整除的正整数。在计算机编程中，判断一个数是否为素数是非常常见的需求。在C++语言中，判断素数的方法有很多种。

方法一：暴力枚举法

暴力枚举法是一种朴素的方法，就是遍历待判断数n的所有可能的因子，判断是否有因子能整除n，如果存在，则n不是素数。这种方法的时间复杂度为O(n)，效率较低。

示例代码：

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

方法二：优化的暴力枚举法

优化暴力枚举法的重点在于：对于一个大于2的整数n，最小的因子肯定不会超过√n，因此只需要枚举到√n即可。这样能够减少判断次数，降低时间复杂度。

示例代码：

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;
}

方法三：埃氏筛法

埃氏筛法是一种筛法，通过筛掉非素数得到素数的方法。首先，将2到n范围内的所有整数标记为素数，然后从2开始，将每个素数的倍数标记为非素数。由于一个合数的最小因子肯定不会超过√n，所以只需要筛到√n即可。

示例代码：

bool isPrime(int n){
  if (n < 2) return false;
  bool is_prime[n + 1];
  memset(is_prime, true, sizeof(is_prime));
  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;
      }
    }
  }
  return is_prime[n];
}

方法四：米勒-拉宾素性检验法

米勒-拉宾素性检验法是一种高效的素数判定方法，适用于大数的判断。其基本原理是：对于任意正整数n，如果n是素数，则有a^(n-1) ≡ 1 mod n，其中a是小于n的随机数。因此，通过随机选择a和验证等式，能够在高概率下判定n是否为素数。由于该方法基于随机数，需要进行多次验证才能保证准确性。

示例代码：

typedef long long LL;
LL q_mul(LL a, LL b, LL mo) {
  LL ret = 0;
  while (b) {
    if (b & 1) ret = (ret + a) % mo;
    a = (a << 1) % mo, b >>= 1;
  }
  return ret;
}
LL q_pow(LL x, LL n, LL mo) {
  LL ret = 1 % mo;
  while (n) {
    if (n & 1) ret = q_mul(ret, x, mo);
    x = q_mul(x, x, mo), n >>= 1;
  }
  return ret;
}
bool Miller_Rabin(LL p) {
  if (p < 2) return false;
  if (p != 2 && p % 2 == 0) return false;
  LL s = p - 1;
  while (s % 2 == 0) s >>= 1;
  for (int i = 0; i < 10; ++i) {
    LL a = rand() % (p - 1) + 1, temp = s;
    LL mod = q_pow(a, temp, p);
    while (temp != p - 1 && mod != 1 && mod != p - 1) {
      mod = q_mul(mod, mod, p);
      temp <<= 1;
    }
    if (mod != p - 1 && temp % 2 == 0) return false;
  }
  return true;
}
bool isPrime(LL n) {
  return Miller_Rabin(n);
}

综上所述，C++判断素数的方法有多种，在实际应用中，应根据需要和数据大小选择最适合的方法，以提高程序效率。

  
  

评论区