算法练习：求质数

算法练习：求质数2014-12-22题目：求质数

内容：

试编写一个程序，找出前N个质数。如果没有进一步要求，这不是难题。但在此希望从所知的、使用除法的方法中，用最快的办法来编写程序。

我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！这个题目确实很简单，先看看常规解法吧！

#include <iostream>#include <math.h>#define endNum 200using namespace std; int _tmain（int argc, _TCHAR* argv[]）{bool isPrime（int x）;cout << endNum << "以内的之所以素数为：" << endl;for （int i = 2; i < endNum; i++）{if （isPrime（i））cout << i << "";}getchar（）;return 0;} bool isPrime（int x）{int endP = sqrt（x）;bool rusult = true;for （int i = 2; i <= endP; i++）{if （（x % i） == 0）{rusult = false;}}return rusult;}

实验结果是

不过题目中要求了思索除法范围内最快的算法，其实就是在循环中，减少以至不为质数的值的除法运算，比如2的倍数，3的倍数，和5的倍数。这样循环的递增就不是按照+1递增了，而已2,4,2,4....循环加法递增，这样可以减少循环三分之二的工作量。

改价算法如下

#include <iostream>#include <math.h>#define endNum 200using namespace std; int _tmain（int argc, _TCHAR* argv[]）{bool isPrime（int x）;int addNum = 2;cout << endNum << "以内的之所以素数为（改进算法）：" << endl;cout << "235";for （int i = 7; i < endNum; ）{if （isPrime（i））cout << i << "";addNum = 6 - addNum;i += addNum;}getchar（）;return 0;} bool isPrime（int x）{int endP = sqrt（x）;bool rusult = true;for （int i = 2; i <= endP; i++）{if （（x % i） == 0）{rusult = false;}}return rusult;}

实验结果：

最后要感谢Clover_tjp同学提出的建议，我会在以后的每日一下练中加以改进，欢迎大家提出自己的意见哈！

作者：csdn博客 u012269327