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

C++中如何判断质数

2023-06-29 19:59:41 深夜i -- --

C++ 判断质数

质数（素数）是指除了1和它本身外，不能被其他自然数整除的自然数。在C++中，判断质数的方法有多种，以下介绍两种常用的方法。

方法一：暴力枚举

暴力枚举的思路是对于每个数，从2开始逐一判断是否能够整除该数，如果不能整除，则该数就是质数。

实现代码如下：


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

该代码首先判断输入的数是否小于等于1（因为1既不是质数也不是合数），如果满足该条件，返回false。否则，对数进行逐一判断，若能够整除，返回false，否则返回true。

虽然暴力枚举的方法思路简单，但是时间复杂度比较高，当输入的数比较大时，运行时间会很长。

方法二：优化筛选

优化筛选的思路是把已经确定是质数的数的倍数排除掉，一次性把所有质数筛选出来。

实现代码如下：


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

该代码首先判断输入的数是否小于等于1（因为1既不是质数也不是合数），如果满足该条件，返回false。否则，对数进行逐一判断，如果该数能够整除它前面的数，则直接返回false。在该方法中，不需要一直判断到n，只需要判断到sqrt(n)，因为一旦大于sqrt(n)的数是n的因数，则必然有小于sqrt(n)的数也是n的因数。这个优化可以大幅减少运行时间。

综上所述，优化筛选方法在时间复杂度上更加优越，能够更快速地判断一个数是否为质数。

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

下一篇: C++中使用头文件cin.getline

评论区

()

相似文章