算法练习：Eratosthenes 筛选法

算法练习：Eratosthenes 筛选法2014-12-22题目：Eratosthenes筛选法

内容：

求质数是一个很普遍的问题，通常不外乎用数去除，除到不尽时，给定的数就是质数。但是早在2000年前人们就知道了一个不必用除法而找出2~N的所有质数的方法。假设一个很神奇的筛子，可以给出一个数，例如i，这个筛子有办法把i所有的倍数去掉。请用这个方法求出2~N之间的所有质数。即Eratosthenes筛选法。

我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！其实就是把后面可以用前面倍数表示的数去掉，因为偶数都包含2，所以只考虑奇数就可以了，这样算法中确实避免了除法，很不错的。

#include <iostream>using namespace std;int main（）{const int lengthOfNum = 201;int x[lengthOfNum] = {1,1};int x_Index = 1;while（x_Index < lengthOfNum）{ if（x[x_Index] == 0）{int j = x_Index+x_Index;while（j < lengthOfNum）{x[j] = 1;j += x_Index;}}x_Index += 2;}cout << lengthOfNum << "以内的所以质数为：" ;cout << "2" ;int x_Index_Print = 1;while（x_Index_Print<lengthOfNum）{if（x[x_Index_Print] == 0）cout << x_Index_Print << "";x_Index_Print += 2;}cout<<endl;return 0;}

实验结果为

作者：csdn博客 u012269327