C++ 素数算法：1000毫秒内找到所有素数 |21xrx.com

C++ 素数算法：1000毫秒内找到所有素数

2023-06-30 01:08:51 深夜i -- --

C++ 素数算法 1000毫秒找到所有素数

C++是一门功能强大的编程语言，它可以被用于各种领域的开发。在数学方面，C++也有许多实用的算法，其中一个就是找到所有的素数。

素数，指的是只能被1和它自身整除的正整数。那么如何使用C++来找到所有的素数呢？其实，这个问题早在古代就被人们探究过，但由于素数数量巨大，无法通过手算来得出所有的素数。而C++编程语言可以帮助我们完成这一任务。

一种简单而高效的算法是使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来找到所有的素数。这种算法基于一个简单的想法：如果一个数是素数，那么它的倍数肯定不是素数。因此，我们可以将所有的自然数初始标记为素数，然后从2开始，将所有2的倍数标记为非素数，接着再从3开始，将所有3的倍数标记为非素数，以此类推，直到所有的倍数都被标记为非素数。

下面是C++代码示例：


#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
int main()
{
  int n=1000000;
  bool prime[n+1];
  for(int i=0;i<=n;i++)
    prime[i]=true;
  clock_t start=clock();
  for(int p=2;p*p<=n;p++)
  {
    if(prime[p]==true)
    {
      for(int i=p*p;i<=n;i+=p)
        prime[i]=false;
    }
  }
  clock_t end=clock();
  for(int i=2;i<=n;i++)
  {
    if(prime[i]==true)
      cout<<i<<" ";
  }
  cout<<endl<<"Time taken: "<<(double)(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;
  return 0;
}

在这段代码中，我们首先定义了一个长度为n+1的布尔数组prime，表示所有数字是否为素数。然后，我们将数组的所有元素初始标记为true。接着，我们使用for循环从2到根号n遍历所有的素数，若该数为素数，则将其倍数标记为非素数。在循环结束后，我们仍然遍历所有数字，输出所有值为true的数字，即为所有的素数。

运行这个程序，可以得到所有1～1000000的素数，并输出程序的运行时间。

总的来说，使用C++语言来完成素数算法非常简单和高效，能够在1000毫秒内找到所有素数。随着计算机技术的普及，我们可以更好地利用编程语言来解决数学问题。

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

下一篇: C++个人音乐库管理系统的程序设计

评论区

()

相似文章