C++中的质数判断方法 |21xrx.com

C++中的质数判断方法

2023-06-24 22:30:13 深夜i -- --

C++ 质数判断方法

在C++中，判断一个数是否是质数是经常需要用到的操作。质数指的是只能被1和自身整除的正整数，比如2、3、5、7等。那么，C++中有哪些方法可以判断一个数是否是质数呢？下面介绍两种常见的方法。

方法一：暴力枚举法。

暴力枚举法是最基本的质数判断方法，即对于一个正整数n，从2开始到n-1依次枚举每个数，判断是否能够被n整除。如果存在一个数能够被n整除，则n不是质数。否则，n是质数。

下面是使用暴力枚举法实现的C++代码：


bool is_prime(int n) {
  if (n <= 1) //根据质数的定义
  for (int i = 2; i < n; i++) { //从2开始到n-1依次枚举每个数
    if (n % i == 0) //如果存在一个数能够被n整除
  }
  return true; //否则，n是质数
}

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

虽然暴力枚举法简单易懂，但是对于大数而言，其时间复杂度较高，会造成程序运行速度变慢。因此，我们可以对暴力枚举法进行一些小的优化，使其运行速度更快。

具体来说，我们只需要枚举从2到n的平方根的整数部分即可。因为如果n有一个大于平方根的因数a，那么必定存在另一个小于平方根的因数b，使得a*b=n，因此只需要枚举到平方根即可。

下面是使用优化的暴力枚举法实现的C++代码：


bool is_prime(int n) {
  if (n <= 1)
    return false;
  
  int sqrtn = (int)sqrt(n); //计算n的平方根
  for (int i = 2; i <= sqrtn; i++) { //从2到n的平方根的整数部分依次枚举每个数
    if (n % i == 0)
      return false;
    
  }
  return true;
}

总结：

以上就是C++中判断一个数是否是质数的两种常见方法：暴力枚举法和优化的暴力枚举法。在实际应用中，应该根据具体情况选择适合的方法。

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

下一篇: C++析构函数何时执行？

评论区

()

相似文章