篩法求質數:
用篩法求質數的基本思想是:把從1開始的、某一範圍內的正整數從小到大順序排列,1不是質數,首先把它篩掉。剩下的數中選擇最小的數是質數,然後去掉它的倍數。依次類推,直到篩子為空時結束。如有:
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
1不是質數,去掉。剩下的數中2最小,是質數,去掉2的倍數,餘下的數是:
3、5、7、9、11、13、15、17、19、21、23、25、27、29
剩下的數中3最小,是質數,去掉3的倍數,如此下去直到所有的數都被篩完,求出的質數為:
2、3、5、7、11、13、17、19、23、29等等。