C++求解质数个数 |21xrx.com

C++求解质数个数

2023-07-01 12:43:49 深夜i -- --

C++ 求解质数个数

在计算机科学领域，质数的概念非常重要。质数是指只能被1和自身整除的正整数，比如2、3、5、7等数值。这种数值很有用，经常用于加密、随机数生成、哈希算法等等领域。在使用C++编程语言时，要求解质数个数是一个常见的任务。下面介绍一种解决问题的方法。

方法一：暴力枚举

暴力枚举方法是最为简单和直接的方法。其基本思路是：从2开始依次枚举每一个数，判断其是否是质数。如果是质数，计数器加1。具体实现如下：


#include <iostream>
using namespace std;
int main()
{
 int n;
 int count = 0;
 bool primeFlag; //记录是否是质数
 cin >> n;
 for (int i = 2; i <= n; i++) {
  primeFlag = true;
  for (int j = 2; j < i; j++) {
   if (i % j == 0)
    primeFlag = false;
    break;
   
  }
  if (primeFlag) count++;
 }
 cout << count << endl;
 return 0;
}

上述程序首先输入需要求解的数据n，然后设定一个计数器count，准备记录质数的个数。接下来，程序从2开始依次进行枚举，每个数都要判断是否为质数。如果是质数，则将计数器加1。最后输出计数器的值即可。

方法二：埃氏筛法

暴力枚举方法适用于小数据范围，但是在大数据范围下，其时间效率显然是不够的。此时，可以采用埃氏筛法，提高效率。

埃氏筛法的基本思路是：先将2~n的所有数列出来，然后从2开始，将素数的所有倍数都标记成合数，然后再从下一个未标记的数（即素数）开始重复此过程。具体如下：


#include <iostream>
using namespace std;
int main()
{
 int n;
 int count = 0;
 bool prime[n + 1];
 for (int i = 2; i <= n; i++) {
  prime[i] = true;
 }
 for (int i = 2; i * i <= n; i++) {
  if (prime[i]) {
   for (int j = i * i; j <= n; j += i) {
    prime[j] = false;
   }
  }
 }
 for (int i = 2; i <= n; i++) {
  if (prime[i]) count++;
 }
 cout << count << endl;
 return 0;
}

上述程序首先输入需要求解的数据n，然后定义一个辅助数组prime[]，用来存储质数的状态，true表示为质数，false表示为合数。接下来，程序对prime[]数组进行初始化，将所有数都设定为质数。然后从2开始，依次判断其是否为质数，如果是，则将其所有倍数都标记为合数。最后再次遍历数组，统计质数的个数。

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

下一篇: C++的push_back()函数

评论区

()

相似文章