21xrx.com
2024-11-22 12:05:51 Friday
登录
文章检索 我的文章 写文章
C++实现求素数的算法
2023-06-27 03:20:55 深夜i     --     --
C++ 素数 算法

素数是只能被1和自身整除的正整数。在数论中,素数是一个非常重要的研究对象。“找到素数”这个问题在计算机科学中也很常见。本文将介绍使用C++实现求素数的算法。

素数的判断方法

要判断一个数是否为素数,最简单的方法是用从2到n-1(或者sqrt(n))的所有整数去除以该数,如果都不能整除,则该数为素数。这个方法的时间复杂度为O(n)或者O(sqrt(n))。

是不是看似很简单?但是使用这种方法判断一个非常大的数是否为素数,则时间复杂度就会非常高。所以我们需要结合其他算法来优化计算。接下来将介绍一种可以快速判断素数的算法 - 埃拉托色尼筛法。

埃拉托色尼筛法

埃拉托色尼筛法是通过逐步筛除每个合数(即不是素数的数)来得到素数。它的基本思路如下:

1. 先将从2开始的所有整数从小到大排列。

2. 取出当前最小的素数2,然后将2的倍数全部标记为合数(即除以2余数为0的数)。

3. 取下一个素数,即没有被标记为合数的下一个数,重复第二步操作。

4. 重复上述步骤,直到已经没有大于等于2的素数为止。

用编程的思路来实现这个算法时,我们可以用一个数组来记录每个数是否为素数,称之为筛子。初始化数组时先将所有的元素初始化为素数,然后从第一个素数即2开始,将2的倍数全部标记为合数,接着移动到下一个没有被标记为合数的素数,将其倍数全部标记为合数。如此循环直到砍到n为止,这时候只有素数的位置上面的数字还是素数,非素数的位置变成了0。具体的代码实现如下:

int prime[10000];

int eratosthenes(int n) {

  int cnt = 0;

  memset(prime, 1, sizeof(prime));

  for (int i = 2; i <= n; i++) {

    if (prime[i]) {

      cnt++;

      for (int j = i * 2; j <= n; j += i) {

        prime[j] = 0;

      }

    }

  }

  return cnt;

}

int main() {

  cout << "小于10的素数个数:" << eratosthenes(10) << endl;

  cout << "小于100的素数个数:" << eratosthenes(100) << endl;

  cout << "小于1000的素数个数:" << eratosthenes(1000) << endl;

  cout << "小于10000的素数个数:" << eratosthenes(10000) << endl;

  return 0;

}

运行结果:

小于10的素数个数:4

小于100的素数个数:25

小于1000的素数个数:168

小于10000的素数个数:1229

从上面的结果可以看出,使用埃拉托色尼筛法能够很快地求出小于某个数的所有素数。

总结

本文介绍了使用C++实现求素数的算法。通过埃拉托色尼筛法,我们可以更快地找到小于某个数的所有素数。当然,如果要判断一个非常大的数是否为素数,还需要更加高效的算法,比如Miller-Rabin素性测试等。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复