用算法求N(N=3)之内素数的个数

本文主要是介绍用算法求N(N=3)之内素数的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先，我们谈一下素数的定义，什么是素数？除了1和它本身外，不能被其他自然数整除（除0以外）的数

称之为素数（质数）；否则称为合数。

根据素数的定义，在解决这个问题上，一开始我想到的方法是从3到N之间每个奇数进行遍历，然后再按照素数的定义去逐个除以3到

根号N之间的奇数，就可以计算素数的个数了。

于是便编写了下面的代码：

（代码是用C++编写的）

#include<iostream>
#include <time.h> 
using namespace std;const int N = 1000000;int compuPrimeN(int);int main(char argc, char* argv[])
{int iTimeS = clock();int iNum = compuPrimeN(N);int iTimeE = clock();cout << iNum << endl;cout << "算法时间:" <<iTimeE - iTimeS<<"毫秒"<< endl;getchar();return 0;
}int compuPrimeN(int maxNum)
{//算法1int iNum = 1;  //起始记上2bool bPrime = true;for (int i = 3; i <= maxNum; i += 2){bPrime = true;for (int j = 3; j <= (int)sqrt(i); j += 2){if (i%j == 0){bPrime = false;break;}}if (bPrime)iNum++;}return iNum;
}

运行后如图所示：

由此可见，算法的性能不是很好，在时间上还有很大可以优化的空间。

那么，该如何优化？

首先，我是想，既然去掉了2的倍数，那么能不能去掉3的倍数，但后来

发现，在第二个循环里第一个取余的就是3，那么3的倍数其实只计算了一次

就过滤，所有没有必要再往下思考。

后来我想到，在第二个循环里，3取余过了，如果没跳出循环，那么6，9之类的

应该不用继续取余，同理，5取余过了，那么10，15...就不该继续取余，因为取余

这篇关于用算法求N(N=3)之内素数的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---