如何在C++中判断质数？ |21xrx.com

如何在C++中判断质数？

2023-06-25 14:37:35 深夜i -- --

C++ 判断质数

质数是指除了1和它本身以外没有其他约数的自然数。在C++中判断一个数是否为质数可以使用以下方法：

方法1：暴力枚举法

暴力枚举法是最基本的判断质数的方法。对于一个正整数n，从2开始一直枚举到n-1，看是否有一个数可以整除n，如果找到，那么n就不是质数。代码如下：


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

方法2：优化枚举法

在暴力枚举法的基础上，可以进行一些优化，提高算法效率。例如，可以只枚举到n的平方根，因为如果n能被大于根号n的数整除，那么它一定能被小于根号n的数整除。另外，还可以对于偶数进行特判，在除以2之后，只需要从3开始枚举奇数即可。代码如下：


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

方法3：厄拉法

厄拉法是一种比较高效的判断质数的方法，在大数的情况下比暴力枚举要快很多。它的原理是根据欧拉定理，如果a和n互质，那么a的phi函数次幂与a的模n同余，即a^(phi(n))≡1(mod n)。我们可以通过这个定理来判断n是否为质数。具体步骤如下：

（1）计算phi(n)，即n的小于n的正整数中与n互质的数的个数。

（2）如果a^(phi(n))≡1(mod n)，则n可能为质数，否则n一定是合数。

代码如下：


int phi(int n) {
  int result = n;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      result = result / i * (i - 1);
      while (n % i == 0)
        n /= i;
      
    }
  }
  if (n > 1) {
    result = result / n * (n - 1);
  }
  return result;
}
bool isPrime(int n) {
  if (n <= 1)
    return false;
  
  int m = phi(n);
  for (int i = 2; i * i <= m; i++) {
    if (m % i == 0)
      return false;
    
  }
  return true;
}

以上就是在C++中判断质数的三种方法，不同的方法适用于不同的场景，可以根据实际情况选择使用。

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

下一篇: 为什么Dev C++没有更新了？

评论区

()

相似文章