C++实现质数判断 |21xrx.com

C++实现质数判断

2023-07-09 07:49:20 深夜i -- --

C++ 实现质数判断

质数是指只能被1和自身整除的正整数。判断一个数是否为质数是计算机程序设计中常见的问题之一。在C++语言中，实现质数判断有多种方法，下面介绍其中两种。

方法一：暴力枚举法

暴力枚举法是最简单的质数判断方法，也是最容易理解的。该方法的基本思路是，对于一个数n，从2到n-1逐个测试其能否整除n，如果能整除，则n不是质数；否则，n是质数。

以下是使用暴力枚举法实现质数判断的C++程序：


#include <iostream>
using namespace std;
bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入一个正整数：";
  cin >> n;
  if (isPrime(n))
    cout << n << "是质数" << endl;
  else
    cout << n << "不是质数" << endl;
  return 0;
}

该程序先定义了一个isPrime函数，用于判断一个数是否为质数。在主函数中，通过输入一个正整数n，调用isPrime函数进行质数判断，输出结果。

方法二：改进的暴力枚举法

暴力枚举法虽然简单易懂，但其时间复杂度较高，在判断较大的数时效率比较低。为了提高效率，一种改进的暴力枚举法被提出。该方法的基本思路是，对于一个数n，仅需要测试其能否被2到n/2之间的数整除，如果能整除，则n不是质数；否则，n是质数。通过缩小判断范围，该方法能在一定程度上提高程序的运行效率。

以下是使用改进的暴力枚举法实现质数判断的C++程序：


#include <iostream>
using namespace std;
bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入一个正整数：";
  cin >> n;
  if (isPrime(n))
    cout << n << "是质数" << endl;
  else
    cout << n << "不是质数" << endl;
  return 0;
}

该程序同样定义了一个isPrime函数，用于判断一个数是否为质数，但测试范围从2到n-1改为了2到n/2，缩小了判断范围。在主函数中，通过输入一个正整数n，调用isPrime函数进行质数判断，输出结果。

总结

通过上述两种方法，实现了C++语言中的质数判断。其中暴力枚举法简单易懂，但在判断较大的数时效率较低；改进的暴力枚举法通过缩小判断范围，能在一定程度上提高程序的运行效率。在实际应用中，应根据不同情况选择相应的方法，以提高程序的效率。

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

下一篇: C++堆和栈的不同点

评论区

()

相似文章