C++实现素数的打印 |21xrx.com

C++实现素数的打印

2023-07-04 08:15:13 深夜i -- --

C++ prime numbers printing

素数是数学中的一种重要的概念，指的是只能被1和自身整除的正整数，如2、3、5、7等都是素数。而使用C++编程实现素数的打印，可以帮助我们更好地理解素数的概念和算法。

首先，我们需要明确素数的判断方法。常见的方法有试除法、埃氏筛法、欧拉筛法等。其中，试除法是最简单粗暴的方法，从2到n-1依次试除n，如果n能被其中任意一个数整除，则n不是素数，否则n是素数。但这种方法效率低，当数值较大时就很难处理。

接下来，我们使用更高效的算法——埃氏筛法来实现素数的判断和打印。埃氏筛法的基本思想是从2开始，将每个素数的倍数都标记成合数，以便后面的数不再重复标记。也就是说，我们可以将所有小于给定值n的素数都找出来，并将它们对应的倍数标记成合数，最后剩下的就是素数了。

下面是使用C++实现埃氏筛法的代码：


#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100000;
int prime[maxn], num = 0; // prime数组用来存储素数，num为素数个数
bool isPrime[maxn]; // 标记是否为素数
void findPrimes(int n) {
  memset(isPrime, true, sizeof(isPrime)); // 初始化为true
  isPrime[0] = isPrime[1] = false; // 排除0和1
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      prime[num++] = i;
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
}
int main() {
  int n = 100;
  findPrimes(n);
  for (int i = 0; i < num; i++) {
    cout << prime[i] << " ";
  }
  cout << endl;
  return 0;
}

上面的代码中，首先定义了一个常量maxn用于存储最大值，以及一个素数数组prime和一个标记数组isPrime。然后定义了一个findPrimes函数，用于找出小于等于n的所有素数并存储在prime数组中。在函数中，我们首先将isPrime数组初始化为true，并排除0和1不是素数的情况。然后利用for循环枚举了所有小于等于n的数，如果该数是素数，则将它加入prime数组中，并将其所有倍数标记为合数，最后输出整个数组即可。

当然，我们也可以在主函数中根据需求输出指定范围内的素数，只需要在调用findPrimes函数之后再增加一层循环即可。总之，使用C++实现素数的打印可以帮助我们更深入地理解素数的概念和算法，也是程序设计中不可或缺的一部分。

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

下一篇: C++中常见的逻辑错误及解决方法

评论区

()

相似文章