Revision 51363 of "埃拉托斯特尼筛法" on zhwikibooks

'''埃拉托斯特尼筛法'''，簡稱'''埃氏篩'''或'''愛氏篩'''，是一種公元前250年由[[古希臘]][[数学家]][[埃拉托斯特尼]]所提出的一種簡單檢定[[素数]]的[[算法]]。

==算式==
给出要筛数值的范围n，找出<math>\sqrt{n}</math>以内的素数<math>p_{1},p_{2},\dots,p_{k}</math>。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一個質數，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一個質數5筛，把5留下，把5的倍数剔除掉；不斷重複下去......。
==两个相等区间的埃拉托斯特尼筛法==
將1至<math>p_{1}p_{2}p_{3}</math>...<math>p_{k-2}p_{k-1}p_{k}</math>连续的自然数按照<math>p_{k-1}p_{k}</math>为一个区间，分为<math>p_{1}p_{2}</math>...<math>p_{k-2}</math>个区间，依次按2，3，5,....順序
篩，篩K次後， 任兩個含連續自然數個數相等的區間，被篩（或末被篩）數相差不超過K。

      說明：本篩法與埃拉托斯特尼篩法不同，埃氏篩先用2篩，然後把2的倍數剔除掉；再用3篩，然後又把3的倍 
  數剔除掉；再用5篩，…。本篩法也是按照2,3,5，...順序篩,用不大於的素數去篩（不得用大於的素數去篩），
只 是已篩過的數數不馬上剔除掉，而是做上標記，等全部篩完過後再把篩過的數剔除掉。於是，有一些含有 幾個不同 素因數的數可能就要被篩幾遍，例如，“6”就要被“2”和“3”各篩一遍。

   證明：根據除法算式定理：“給定正整數a和b，b≠0，存在惟一整數b和q，使a=bq+r”得知，如果
從a中篩 bm形數，a個連續自然數中，最多含有q個bm形數，r個連續自然數中，最多含有1個形數。

   例如a=35，b=3。 35個連續自然數中最多含有11+1=12個3m形數。如36—70有12個3m形數，1－35
有11個3m形數。

   現在設某兩個區間為A與B，含自然數的個數分別為|A|與|B|，|A|=|B|，下證明P去篩，兩個區間被
篩形數（或 未被篩數）個數相差最多不超過1，由上所述篩法，用順序素數2,3,5,..依次去篩，兩個區間每次被篩形數 （或未被篩數） 個數相差最多不超過1，故篩次兩區間被篩數（或未被篩數數）個數最多不超過個。

   證法（1），設|A|=a=bq+r,則|B|=a=bq+r，即區間A和B中均至少含有q（q>1）個bm形數，又由於
r<b，故r個連續 自然數中至多有一個形數，即被篩bm形個數相差不超過1。

   證法（2），假若不然，篩K次有兩個區間A與B，被篩數相差大於K，比如有K+1個，那會出現現什麼
問題呢？我們問第是個什麽數，見圖，假如與用2和3篩，如果出現了相差3個，第一個記為形，第二個記為形，問第三個（？ ）是什麼形式，（每一方括号表示一個自然數，）。

   A：[][]...[] --------------------------- [][][][][][] 
   
  B：[][]...[][2m][3m][？]-------------------[][][] 
   
       已篩過部分--------------------   未篩過部分 
  
   如果第三個（？）是2m或3m形，顯然與除法算式定理矛盾；如果不是2m或3m形，它就不應“站在”
已篩過部分行列，無論哪種情況，假設都不成立，證畢。

 为什么区间要大于 <math>2p_{k}</math>
  如果区间小于<math>2p_{k}</math>，并且不按照顺序筛法，就会出现其它异常。例如，我们直接用5和
7筛，区间为2×5-1=9个自然数；

  A区间：31,32,33,34,35,36,37,38,39；（用5和7筛，只筛掉35） 
  
  B区间：13,14,15,16,17,18,19,20,21.（用5和7筛，筛掉14,15,20,21有四个）。 
   
  筛2次相差3个。如果先用2和3筛过，实际上只是相差1个（35）。B区间实际上都是已经筛过的。如果区间
加大一个自然数， 使得区间≥，上面构造就不能成立。 筛法里面有许许多多问题值得研究。
'''中国科学院数学家认为这是一个显然的事实'''
==参考资料==
《数学之恋》