C++编写素数判断程序 |holyya.com

C++编写素数判断程序

2023-07-10 03:28:45 深夜i -- --

C++ 素数判断程序

C++是一种流行的编程语言，经常用于编写高效的程序。在数学和计算机科学中，素数是一类特殊的数字，它只能被1和自己整除。在本文中，我们将使用C++编写一个简单的程序，来判断一个数字是否为素数。

一般来说，判断一个数字是否为素数，最标准的方法是试除法。也就是，对于一个数字n，依次除以小于n的每一个数字，如果除尽了，那么n就不是素数。否则，n就是素数。但是这种方法在效率上有些欠缺，特别是在处理大数字的时候。因此我们采用更加高效的算法：埃拉托斯特尼筛法。

埃拉托斯特尼筛法，简称埃氏筛，是一种生成素数的算法。它的基本思想是：从2开始，依次筛去2的倍数、3的倍数、4的倍数……一直到不超过n的所有素数。这种方法的优点是可以大大减小计算量，其时间复杂度为O(nloglogn)。

下面就是一个简单的C++程序，使用埃氏筛法来判断一个数字是否为素数：


#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n) {
  if (n <= 1)
    return false;
  
  bool prime[n + 1];
  for (int i = 2; i <= n; i++) {
    prime[i] = true;
  }
  for (int i = 2; i <= sqrt(n); i++) {
    if (prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  return prime[n];
}
int main() {
  int n;
  cout << "请输入一个数字: ";
  cin >> n;
  if (is_prime(n))
    cout << n << " 是素数。" << endl;
   else
    cout << n << " 不是素数。" << endl;
  
  return 0;
}

程序中的 is_prime 函数接受一个整数 n，返回一个布尔值，表示 n 是否为素数。首先，判断如果 n 小于或等于 1，那么它就不是素数，直接返回 false。接下来，使用一个 bool 类型的数组 prime 来记录每个数字是否为素数。数组 prime 先被初始化为 true。

然后，我们使用一个嵌套的循环来实现埃氏筛。外层循环从 2 开始，一直遍历到 n。内层循环从外层循环变量的平方开始，每次增加外层变量的值。这样就能够筛去小于或等于 n 的所有合数。如果 prime[n] 是 true，那么 n 就是素数，返回 true。否则，返回 false。

最后，在主函数中，输入一个数字 n，调用 is_prime 函数来判断它是否是素数，并输出结果。

通过这个简单的C++程序，我们可以深入理解素数判断的算法实现，并了解C++的语法和程序设计思路。

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

下一篇: C++实现10个评委打分的while循环语句

评论区

()

相似文章