C++求素数个数 |21xrx.com

C++求素数个数

2023-07-07 14:08:43 深夜i -- --

C++ 素数个数判断循环

素数是指只能被1和本身整除的自然数，如2、3、5、7、11等，而4、6、8等就不是素数。在实际开发中，求素数个数是一个比较常见的需求。下面我们就来介绍一下使用C++语言来求素数个数的方法。

方法一：暴力求解

暴力求解法是最简单、最基本的方法，也是最容易理解的方法，具体步骤如下：

1.遍历2到给定范围内的所有自然数。

2.判断每个自然数是否为素数，如果是素数，则记录下来。

3.统计素数的数量即可。

下面是使用C++语言实现的代码：


#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int n)
{
  if(n<=1) return false;
  for(int i=2;i<=sqrt(n);i++)
    if(n%i==0) return false;
  return true;
}
int main()
{
  int n,count=0;
  cin>>n;
  for(int i=2;i<=n;i++)
    if(isprime(i)) count++;
  cout<<count<<endl;
  return 0;
}

在该代码中，isprime函数用于判断一个数是否为素数，其返回值为true或false。具体实现方式就是从2开始枚举到sqrt(n)为止，看是否有数能整除n。如果有就说明n不是素数，返回false；否则说明n是素数，返回true。

在主函数中，先输入一个数n，然后依次判断2到n中的每个数是否为素数，如果是素数，则素数个数自增1，最后输出素数个数即可。

方法二：筛法求解

与暴力求解法不同，筛法求解法通过对自然数进行筛选，可以更快地求出素数个数。具体步骤如下：

1.从2开始，将每一个素数的倍数都标记成合数，标记方法为用该素数去乘2，3，4等来标记合数。

2.找下一个素数。素数可以是未被标记成合数的最小自然数。重复步骤1，直到所有素数都被找到为止。

3.对标记为素数的数进行计数。

下面是使用C++语言实现的代码：


#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=100000;
bool isprime[MAXN+1];
int sieve(int n)
{
  int p=0;
  memset(isprime,true,sizeof(isprime));
  isprime[0]=false,isprime[1]=false;
  for(int i=2;i<=n;i++)
    if(isprime[i])
    {
      p++;
      for(int j=i*i;j<=n;j+=i)
        isprime[j]=false;
    }
  return p;
}
int main()
{
  int n;
  cin>>n;
  cout<<sieve(n)<<endl;
  return 0;
}

在该代码中，sieve函数用于实现筛法求素数的方法，其参数n表示需要求出素数的范围。在该函数中，首先将所有自然数标记为素数(isprime[i]=true)，然后将0和1标记为合数(isprime[0]=false,isprime[1]=false)。接着，从2开始遍历每个数，如果这个数是素数，就将它的所有倍数都标记成合数。最后统计所有素数的数量即为筛法求解法求出的素数个数。

在主函数中，先输入一个数n，然后调用sieve函数求解素数个数，最后输出素数个数即可。

总之，求素数个数是一道比较常见的算法问题，通过使用C++语言，可以实现多种方法来求解该问题，本文介绍的暴力求解法和筛法求解法就是其中比较常见的两种方法。无论采用哪种方法，都可以通过这种方式来提高我们对C++语言的理解和掌握。

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

下一篇: C代码转C++工具

评论区

()

相似文章