Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:AC了,帖一些关于这道题的介绍吧。

Posted by risyomei at 2008-08-26 10:30:32 on Problem 3006
In Reply To:AC了,帖一些关于这道题的介绍吧。 Posted by:humanjustic at 2006-11-16 17:31:07
> 1640年,法国的业余数学家费尔玛指出,N为非负整数时,F(N)=2 2 n+1是一个素数。可是他并没有给出证明。1732年,数学家欧拉指出,当N=5时,F(5)=2 2 5+1=641*6711417,F(N)又是一个合数。
>   1873年德国数学家狄利克雷试图证明下列定理,设A与D为互素的整数,由算术级数A,A+B,A+2D,A+3D,……可得到无限多个素数。他的证明取得了巨大的成功,但是证明过程非常难懂,没有几个人能够接受。
>   在这一方面最大的成就是素数定理,它是由德国大数学家高斯提出来,最终由法国人阿达马和比利时人普车在1896年各自独立地证明的。
>   1947年,数学家米尔斯证明了存在这样的一个实数A,它使得不超过A 3 n的最大的整数,于每一个正整数N都是素数。可是,对于实数A的实际取值,即使是一个大概的取值,谁也无法说清楚。
> 
> “埃拉托尼筛子”法:
> 他首先从2开始,写出自然数:2,3,4,5,6,7,8,9…100,然后,把其中的一切合数划去,划掉合数的原则是,在这一列数中,第一个数2满足素数的定义,把它保留下来。随后把能被2整除的数都划去,因为它们都是合数。接着在数2后的没有被划去的第一个数是3,因为它只被1和它本身整除,所以它是一个合数,把它也划去。剩下没有被划去的第一个有选举权是5,它只能被这和它本身整除,所以它也是一个素数。如此连续不断地划下去,最后剩下的数都是素数。
>   为什么把这种方法叫做“厄拉多塞筛子”呢?因为厄拉多塞在求素数时,把自然数写在一块白蜡的木板上,并逐个在写着合数的位置上刺一个孔,这样白蜡板上被刺了很多的小孔,好像一个筛子。把所有的合数“筛掉”剩下的就都是素数。
> 
> 
> Problem Id:3006  User Id:humanjustic 
> Memory:88K  Time:264MS
> Language:C++  Result:Accepted
> 
> 


好!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator