数学百科

广告

你知道什么是筛法?

2011-07-19 07:05:29 本文行家:gjc

&n

                                                                              筛法


图片 1图片 1


  筛法,是求不超过自然数n(n>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~前194年)发明的,又称埃拉托斯特尼筛子。

  具体做法是:先把n个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数,留下来,而把2后面所有2的倍数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有3的倍数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有5的倍数都划去。这样一直做下去,就会把不超过n的全部合数都筛掉,留下的就是不超过n的全部质数。因为希腊人是把数写在涂蜡的板上,每划去一个数,就在上面记以小点,寻求质数的工作完毕后,这许多小点就像一个筛子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”,简称“筛法”。(另一种解释是当时的数写在纸草上,每划去一个数,就把这个数挖去,寻求质数的工作完毕后,这许多小洞就像一个筛子。)

  例如,用筛法找出不超过30的一切质数:

  1  2  3  4  5  6  7  8  9  10

  11  12  13  14  15  16  17  18  19  20

  21  22  23  24  25  26  27  28  29  30

  因此,不超过30的质数有:2,3,5,7,11,13,17,19,23,29,共10个。
百科的文章(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。如需转载,请注明来源于www.baike.com
广告

本文行家向Ta提问

gjc程召河,男,1995年毕业于济南师范,小学高级教师。现任济阳县第二实验小学政教主任、数学教师。 自2008年9月负责学校少先队工作以来取得了优异的成绩。2009年获济阳县“优秀教师”、济南市“环境教育优秀教师”、“市优秀班主任”等称号。 2010年,获济阳县“争当四好少年”演讲“优秀指导教师”、小学生乒乓球“优秀教练员”、“少先队工作先进个人”等称号;2011年3月,被评为《山东少先队》“优秀通讯员”。由于负责的少先队工作出色,2010年学校被评为济阳县少先队工作示范校、济阳县第一届道德模范集体、二0一0年度科学发展先进单 ...