ca26a_demo埃拉托斯特尼_筛法_标准库 bitset应用实例

/* 埃拉托斯特尼_筛法,ca26a_demo.txwtech20200126 标准库 bitset应用实例 “筛法”，用来查找质数（素数，只能被1和自身整出的数），早在两千年前就被希腊数学家埃拉托斯特尼（Eratosthenes）发现了。它的原理是什么呢？其实非常简单，花一分钟你就能明白。2，3，5，7，11.  用于寻找到很大的质数进行加密。几百位的质数,880000,6位就是88w. 先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。 第二个数2是质数留下来，而把2后面所有能被2整除的数都划去，“划去”就是把二进制位1变成0。 2后面第一个没有划去的数是3，把3留下来，再把3后面所有能被3整除的数划去。 3后面第一个数没有划去的数是5，把5留下来。 再把5后面所有能被5整除的数都划去. 这样一直做下去，就会把不超过N的全部合数都筛掉。留下的就是不超过N的全部质数。

因为希腊人把数写在涂腊的板上，没要划去一个数，就在上面记以小点， 寻求质数的工作完毕后，这许多小点就像一个筛子，所以就形象的把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。 */

/* 埃拉托斯特尼_筛法,ca25a_demo.txwtech20200126
标准库 bitset应用实例
“筛法”，用来查找质数（素数，只能被1和自身整出的数），早在两千年前就被希腊数学家埃拉托斯特尼（Eratosthenes）发现了。它的原理是什么呢？其实非常简单，花一分钟你就能明白。2，3，5，7，11. 
用于寻找到很大的质数进行加密。几百位的质数,880000,6位就是88w.
先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。
第二个数2是质数留下来，而把2后面所有能被2整除的数都划去，“划去”就是把二进制位1变成0。
2后面第一个没有划去的数是3，把3留下来，再把3后面所有能被3整除的数划去。
3后面第一个数没有划去的数是5，把5留下来。
再把5后面所有能被5整除的数都划去.
这样一直做下去，就会把不超过N的全部合数都筛掉。留下的就是不超过N的全部质数。

因为希腊人把数写在涂腊的板上，没要划去一个数，就在上面记以小点，
寻求质数的工作完毕后，这许多小点就像一个筛子，所以就形象的把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。
*/
#include 
#include  //标准库
#include //sqrt
using std::cout;
using std::endl;

int main()
{
	int const max_number(100);//定义一个常量，比max_number=100,方式速度快。
	int const max_test((int)sqrt((double)max_number));//参数转型double，结构转型int.
	//定理：非质数的特性，合数的特性：
	//任何非质数至少有一个因数不会大于它的平方根。
	//如：所有小于100的非质数，至少有一个小于10的因数
	std::bitset numbers;//101个0
	numbers.set();//设置为101个1；
	numbers[1] = 0;
	//for (int i(1); i != 100; i++)
	for (int i(1); i != max_test; i++)
	{
		if (numbers[i])
		{
			//筛掉倍数作用方法1：2的倍数
			//for (int j = i * 2; j < max_number + 1; j += i)
			//筛掉倍数作用方法2：i的平方
			for (int j (i * i); j < max_number + 1; j += i)
			{
				numbers[j] = 0;//把所有相关倍数置0
			}
		}
	}
	cout