C++如何判断一个数是否为素数 |21xrx.com

C++如何判断一个数是否为素数

2023-06-22 15:41:18 深夜i -- --

C++ 判断数素数

素数是指除了1和它本身以外，没有其他正整数可以整除它的数。因此，判断一个数是否为素数是很重要的数学问题。在编程方面，这是一个经典的问题，常用于程序设计竞赛和算法研究。本文将介绍C++如何判断一个数是否为素数。

一般而言，判断素数的方法有两种：试除法和质数筛法。试除法是最简单和直接的做法。对于任意一个自然数n，用2~√n范围内的所有整数去除n，如果都不能整除，则n为素数。此方法的时间复杂度为O(√n)。C++代码如下：


bool isPrime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

其中，isPrime函数返回值为bool类型，表示n是否为素数。首先判断n是否小于2，因为小于2的数不是素数。接着，用从2到√n的范围内的数去除n，判断是否能整除n，如果能则不是素数，返回false；反之，则是素数，返回true。

质数筛法是解决大量查询素数问题的有效方法，它通过预处理出一定范围内所有的素数，然后查询是否是这个范围内的素数。质数筛法的时间复杂度为O(nloglogn)。常用的筛法有欧拉筛和埃拉托色尼筛。这里以埃拉托色尼筛为例，介绍C++代码实现。


void eratosthenes(int n, vector<int>& primes) {
  vector<bool> isPrime(n + 1, true); // 初始化所有数为素数
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push_back(i); // i是素数，加入素数列表
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false; // 将i的倍数标记为不是素数
      }
    }
  }
}

其中，eratosthenes函数用来求解[2, n]范围内的素数，将素数存入primes数组中。首先，定义一个长度为n+1的bool数组isPrime，初始化所有数为素数。从2开始，依次遍历到n，如果当前数是素数，将其存入primes数组中，然后将其所有的倍数都标记为不是素数。标记的方法是从i的平方开始，依次加上i，直到大于n。

总的来说，判断一个数是否为素数的方法有试除法和质数筛法两种。试除法是简单直接的方法，适用于查询范围较小的素数；质数筛法则是预处理素数列表，避免重复计算，适用于大量查询素数的场景。在实现过程中，需要注意判断小于2的数不是素数，以及遍历范围取2~√n或2~n的区别。

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

下一篇: 如何解决Visual C++错误？

评论区

()

相似文章