１６４０年，法国的业余数学家费尔玛指出，Ｎ为非负整数时，Ｆ（Ｎ）＝2 2 n+1是一个素数。可是他并没有给出证明。１７３２年，数学家欧拉指出，当Ｎ＝５时，Ｆ（５）=2 2 5+1=641*6711417,F(N)又是一个合数。
　　１８７３年德国数学家狄利克雷试图证明下列定理，设Ａ与Ｄ为互素的整数，由算术级数Ａ，Ａ＋Ｂ，Ａ＋２Ｄ，Ａ＋３Ｄ，……可得到无限多个素数。他的证明取得了巨大的成功，但是证明过程非常难懂，没有几个人能够接受。
　　在这一方面最大的成就是素数定理，它是由德国大数学家高斯提出来，最终由法国人阿达马和比利时人普车在１８９６年各自独立地证明的。
　　１９４７年，数学家米尔斯证明了存在这样的一个实数Ａ，它使得不超过A 3 n的最大的整数，于每一个正整数Ｎ都是素数。可是，对于实数Ａ的实际取值，即使是一个大概的取值，谁也无法说清楚。

“埃拉托尼筛子”法：
他首先从２开始，写出自然数：２，３，４，５，６，７，８，９…１００，然后，把其中的一切合数划去，划掉合数的原则是，在这一列数中，第一个数２满足素数的定义，把它保留下来。随后把能被２整除的数都划去，因为它们都是合数。接着在数２后的没有被划去的第一个数是３，因为它只被１和它本身整除，所以它是一个合数，把它也划去。剩下没有被划去的第一个有选举权是５，它只能被这和它本身整除，所以它也是一个素数。如此连续不断地划下去，最后剩下的数都是素数。
　　为什么把这种方法叫做“厄拉多塞筛子”呢？因为厄拉多塞在求素数时，把自然数写在一块白蜡的木板上，并逐个在写着合数的位置上刺一个孔，这样白蜡板上被刺了很多的小孔，好像一个筛子。把所有的合数“筛掉”剩下的就都是素数。


Problem Id:3006  User Id:humanjustic 
Memory:88K  Time:264MS
Language:C++  Result:Accepted

• Re:AC了，帖一些关于这道题的介绍吧。 (862) risyomei 2008-08-26 10:30:32