C++中素数判断方法及代码 |21xrx.com

C++中素数判断方法及代码

2023-07-04 09:30:49 深夜i -- --

C++ 素数判断代码

素数在数学中有着重要的地位，而在编程中，也经常需要判断一个数是否为素数。在C++中，判断素数的方法有很多种，下面将介绍其中两种常用的方法，以及对应的代码。

方法一：试除法

试除法是一种判断素数的基础方法，其原理是：对于一个正整数n，如果存在一个正整数x(1

基于这个原理，我们可以使用for循环进行遍历，若n能被某个x整除，则n不是素数，否则n是素数。

下面是使用试除法判断素数的C++代码：


bool isPrime(int n) {
  if (n <= 1) return false; // 小于等于1的数不是素数
  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false; // n能被i整除，说明n不是素数
  }
  return true;
}

方法二：埃拉托色尼筛法

埃拉托色尼筛法是一种比试除法更为高效的方法，其基本思想是：从2开始，将每个素数的倍数都标记成合数，直到没有未标记的素数为止，就得到了所有的素数。

例如，要求10以内的素数，我们可以将2、3、5标记为素数，其余的数为合数，这样得到的素数序列为2、3、5、7。

下面是使用埃拉托色尼筛法判断素数的C++代码：


bool isPrime(int n) {
  if (n <= 1) return false; // 小于等于1的数不是素数
  vector<bool> is_primes(n + 1, true); // 初始化全部为素数
  for (int i = 2; i * i <= n; i++) {
    if (is_primes[i]) { // 如果i是素数，则标记i的倍数为合数
      for (int j = i * i; j <= n; j += i) {
        is_primes[j] = false;
      }
    }
  }
  return is_primes[n];
}

总结：

以上介绍了C++中两种判断素数的常用方法及其对应的代码。虽然试除法比较简单，但其时间复杂度高，而埃拉托色尼筛法则相对简单而高效。在实际应用中，可以根据具体情况选择合适的方法。

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

下一篇: Dev C++编写求解三角形面积的程序

评论区

()

相似文章