C++ 如何找到素数？ |21xrx.com

C++ 如何找到素数？

2023-06-29 20:36:13 深夜i -- --

C++ 素数寻找

C++是一种非常流行的编程语言，它可以用来解决许多复杂的算法问题，其中一个常见的问题就是找素数。在C++中，有许多不同的方法可以找到素数，下面我们就来介绍一些常用的方法。

首先，我们可以使用最简单的方法来找素数，即遍历每个数字，并检查它是否是素数。这种方法的时间复杂度很高，但它是最基本的一种方法。具体实现如下：

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

在上面的代码中，我们首先判断输入的数字是否小于等于1，因为小于等于1的数字都不是素数。然后我们遍历2到根号n之间的所有数字，检查它是否能被n整除。如果有一个数字能被n整除，那么n就不是素数。如果没有这样的数字，那么n就是素数。

接下来，我们来介绍另一种方法，在使用这种方法时，我们需要用到一个数学定理：除2以外的任何偶数都不是素数。这意味着我们可以在遍历数字时先跳过所有偶数。具体实现如下：


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

在上面的代码中，我们首先判断输入数字是否小于等于1，如果是，那么它肯定不是素数。然后，我们检查输入数字是否等于2，如果是，那么它就是素数。接着，我们判断输入数字是否为偶数，如果是，那么它也肯定不是素数。最后，我们遍历所有奇数，检查它是否能被n整除。

接下来，我们来介绍一种更高效的算法，它叫做埃氏筛法。这种算法可以帮助我们快速找到指定范围内的所有素数。具体实现如下：


vector<int> getPrimes(int n) {
  vector<bool> isPrime(n+1, true);
  vector<int> primes;
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push_back(i);
      for (int j = 2 * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return primes;
}

在上面的代码中，我们首先创建一个长度为n+1的数组，用来表示每个数字是否为素数。然后我们遍历2到n之间的每个数字，如果当前数字i是素数，那么我们把它加入primes数组中，同时标记所有i的倍数为非素数。最后，我们返回primes数组，它包含指定范围内的所有素数。

总结

在C++中，有许多不同的方法可以找到素数，我们可以根据实际情况选择合适的方法。如果我们只需要找单个数字是否为素数，那么最简单的方法就足够了。如果我们需要找指定范围内的所有素数，那么埃氏筛法可能是最好的选择。而如果我们需要经常进行素数判断，可以将素数表都预处理出来，然后使用二分等技巧查找。无论怎样，C++都非常适合这些问题的解决。

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

下一篇: C++多态实例：实践中的应用与案例

评论区

()

相似文章