首页 > 代码库 > 每日一小练——Eratosthenes 筛选法

每日一小练——Eratosthenes 筛选法

上得厅堂。下得厨房。写得代码,翻得围墙,欢迎来到睿不可挡的每日一小练!


题目:Eratosthenes筛选法


内容:

求质数是一个非常普遍的问题,通常不外乎用数去除。除到不尽时,给定的数就是质数。

可是早在2000年前人们就知道了一个不必用除法而找出2~N的全部质数的方法。如果一个非常奇妙的筛子,能够给出一个数。比如i,这个筛子有办法把i全部的倍数去掉。

请用这种方法求出2~N之间的全部质数。即Eratosthenes筛选法。

我的解法:上来没多想。打开vs2013就敲了起来。问题果然非常easy,分分钟就超神。

。奥。不正确就攻克了。事实上就是把后面能够用前面倍数表示的数去掉,由于偶数都包括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;
}

实验结果为

技术分享


欢迎大家增加每日一小练,嘿嘿!

每天练一练,日久见功夫,加油。


            -End-

參考文献:《c语言名题精选百则》


每日一小练——Eratosthenes 筛选法