C++实现素数计算 |21xrx.com

C++实现素数计算

2023-07-14 10:07:23 深夜i -- --

C++ 素数计算算法循环

素数，是指除了1和它本身之外无法被其它数整除的正整数，比如2、3、5、7等。素数在计算机领域中运用广泛，比如加密算法、哈希表等。而在编程语言中，C++也提供了实现素数计算的功能。

C++实现素数计算的方法有多种，以下是其中的两种常见方法：

1.暴力枚举法

最简单的计算所有小于n的质数的方式是“试除法”或“暴力枚举法”，即将每个数 2 ≤ p ≤ n 与所有小于 p 的数相除，如果能被整除则说明不是素数，否则是素数。

下面是C++代码实现：


bool isPrime(int n) {
  if(n<=1) return false; //小于等于1不是素数
  for(int i=2;i<n;i++) {
   if(n%i==0) return false; //有因子则不是素数
  }
  return true;
}

2.筛选法

筛法是一种基本的质数筛法，它能够筛选出素数。首先构造一个2-n的集合，然后先把2添到素数表，把2的倍数从集合中删去；接下来是3，如3没有被删去，把它加到素数表中，把3的倍数删去；接下来是5，把5加到素数表中，把5的倍数删去......接下来持续重复这个过程，直到筛选完2-n里所有的素数。最终结果即为小于n的素数。

以下是C++代码实现：


void getPrimes(int n,bool *isPrime) {
  for(int i=2;i<=n;i++) isPrime[i]=true; //初始化数组
  for(int i=2;i<=n;i++) {  //从2开始枚举
    if(isPrime[i]) {  //如果i是素数，则将i的倍数标记为非素数
      for(int j=2*i;j<=n;j+=i) {
        isPrime[j]=false;
      }
    }
  }
}

使用isPrime[n]数组来记录每个数是否为素数，true表示是素数，false表示不是素数。在每次计算时，从2开始枚举每个数i，如果isPrime[i]为true，则i为素数，将i的倍数标记为非素数。

以上两种方法各有优缺点，暴力枚举法实现简单，但是当n较大时，时间复杂度较高，不能满足大规模计算。而筛选法较为高效，可以筛选出比较大的素数，但是需要额外的内存存储isPrime数组。

总的来说，C++实现素数计算的方法多种多样，开发者可以根据具体需求选择最合适的方案，实现高效、准确的素数计算。

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

下一篇: C++静态库能否做到跨平台？

评论区

()

相似文章