Eratosthenes篩法(Sieve)

13579,1234566891都是質數,有沒有一個判斷的演算法(algorithm)?古希臘數學家Eratosthenes (276~194 BC)提出一個找出小於某數的所有質數的方法.叫做Eratosthenes篩法(Sieve).例如,求小於100的質數
  1. 列出2~100
  2. 第一個質數是2,除了2以外,把所有2的倍數都刪掉
  3. 下一個沒有被刪掉的數是3,除了3之外,把所有3的倍數都刪掉
  4. 下一個沒有被刪掉的數是5,除了5之外,把所有5的倍數刪掉
  5. ...,以此類推,保留下一個未被刪掉的數,把它的倍數刪掉
  6. 最後剩下來的數2,3,5,7,...,97就是小於100的質數
Eratosthenes篩法(Sieve)的另一種表現,以2543為例
  2. 先找出小於51的質數2,3,5,7,11,13,17,19,23,29,31,37,41,43,47
  3. 2543除以上面15個數,結果都不能整除
  4. 如果   p,q皆大於51,則,矛盾,所以如果2543不是質數,就有小於51的質因數,由2.矛盾

因此,我們知道2543是質數