C++ 求解质数问题 |21xrx.com

C++ 求解质数问题

2023-06-27 13:12:05 深夜i -- --

C++ 求解质数问题素数判断埃氏筛法

质数，又称素数，是指除了1和本身以外没有其他因数的自然数。求解质数一直是计算机领域中非常重要的问题，在计算机算法中有着广泛的应用。C++语言作为计算机领域中最重要的语言之一，提供了多种方法来求解质数问题。

在C++语言中，我们可以使用传统的暴力枚举法来求解质数，即判断2到n-1 中是否有n的因数。但是这样的方法时间复杂度较高，当n较大时会导致运行速度非常慢，因此在实际应用中并不常用。

更为高效的方法是埃拉托斯特尼(Eratosthenes)筛法和欧拉(Euler)筛法。

埃拉托斯特尼筛法的原理是，先生成一个2到n的整数序列，在序列中找出最小的质数2，然后将序列中2的倍数（除2以外）全部标记成非素数，接着从已标记的数后面找到下一个质数3，然后将3的倍数（除3以外）全部标记成非素数，依次进行此操作直到序列末尾。最后，未被标记的数即为质数。这种算法的时间复杂度为 O(nlog(log(n)))。

欧拉筛法是对埃氏筛法的优化。它使用了线性筛法，并将质数和合数的判别合并到了一起，因此时间复杂度更低，为O(n)。具体实现方法可以参考以下代码：


bool isPrime[N];
int prime[N], cnt = 0;
void getPrimes(int n) {
  memset(isPrime, true, sizeof isPrime); // 初始化为true，即假设所有数都为质数
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) prime[++cnt] = i; // 如果是质数，加入到质数数组中
    for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
      isPrime[i * prime[j]] = false; // 将当前数标记为合数
      if (i % prime[j] == 0) break; // 如果i是质数，且能整除质数j，直接退出循环
    }
  }
}

总之，C++提供了多种方法来求解质数问题，我们已经介绍了其中两种常见的方法——埃拉托斯特尼筛法和欧拉筛法。在实际编程中，需要根据具体情况选择使用不同的方法，以便更高效、更快地解决质数问题。

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

下一篇: C++多重继承简介

评论区

()

相似文章