用C++函数判断输入的一行数中素数的个数 |21xrx.com

用C++函数判断输入的一行数中素数的个数

2023-07-05 12:12:32 深夜i -- --

C++ 函数输入素数个数

要判断输入的一行数中素数的个数，可以采用C++函数来实现。首先需要明确什么是素数。

素数是指只能被1和自身整除的正整数。我们可以用循环的方式依次判断每个数是否为素数。但是这种方法很容易超时，对于大量数据的判断就不可取。因此，我们可以优化这个过程，采用“埃氏筛法”。

埃氏筛法是一种常见的筛法，可以用来求素数。筛法的思想是从2开始，将每个质数的倍数都标记成合数。我们可以定义一个数组来标记一个数是否为素数，然后遍历数组，将每个素数的倍数标记为合数。最后统计素数的个数输出即可。

下面是采用C++函数实现判断素数的代码：


#include <iostream>
#include <cmath>
using namespace std;
void isPrime(int num)
{
  int cnt = 0; // 素数计数器
  bool isComposite[num+1] = {0}; // 初始化为false
  // 遍历2到num
  for(int i=2; i<=num; i++)
  {
    // 如果这个数还没有标记为合数
    if(!isComposite[i])
    {
      cnt++; // 素数计数器加1
      // 枚举这个数的倍数并标记为合数
      for(int j=i*i; j<=num; j+=i)
        isComposite[j] = true;
    }
  }
  cout << "素数的个数为：" << cnt << endl;
}
int main()
{
  int num;
  cout << "请输入一个正整数：";
  cin >> num;
  isPrime(num);
  return 0;
}

以上代码中，我们使用了bool数组来记录每个数是否为素数。初始化为false，代表所有数都是素数。然后从2开始遍历，如果发现一个数没有被标记为合数，则计数器加1，同时将它的倍数都标记为合数。最后统计素数的个数并输出。

需要注意的是，我们使用了sqrt函数来对枚举的倍数进行优化。因为如果一个数不是素数，它一定是由两个大于sqrt(num)的自然数相乘得到的。因此，我们只需要枚举到sqrt(num)即可。

总之，使用C++函数判断输入的一行数中素数的个数，是一种简单而有效的方法。可以帮助我们更快速地解决问题。

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

下一篇: VC++6.0编写的爱心代码带有彩色效果

评论区

()

相似文章