篩選求質(zhì)數(shù)

明除了自身之外，無法被其它整數(shù)整除的數(shù)稱之為質(zhì)數(shù)，要求質(zhì)數(shù)很簡單，但如何快速的求出質(zhì)數(shù)則一直是程式設(shè)計人員與數(shù)學(xué)家努力的課題，在這邊介紹一個著名的 Eratosthenes求質(zhì)數(shù)方法。

首先知道這個問題可以使用回圈來求解，將一個指定的數(shù)除以所有小于它的數(shù)，若可以整除就不是質(zhì)數(shù)，然而如何減少回圈的檢查次數(shù)？如何求出小于N的所有質(zhì)數(shù)？首先假設(shè)要檢查的數(shù)是N好了，則事實上只要檢查至N的開根號就可以了，道理很簡單，假設(shè)A*B = N，如果A大于N的開根號，則事實上在小于A之前的檢查就可以先檢查到B這個數(shù)可以整除N。不過在程式中使用開根號會精確度的問題，所以可以使用 i*i <= N進(jìn)行檢查，且執(zhí)行更快。

再來假設(shè)有一個篩子存放1～N，例如：

23 456789101112131415161718192021 ....N

先將2的倍數(shù)篩去：

23 579111315171921....N

再將3的倍數(shù)篩去：

23 5711131719....N

再來將5的倍數(shù)篩去，再來將7的質(zhì)數(shù)篩去，再來將11的倍數(shù)篩去........，如此進(jìn)行到最后留下的數(shù)就都是質(zhì)數(shù)，這就是Eratosthenes篩選方法（Eratosthenes Sieve Method）。檢查的次數(shù)還可以再減少，事實上，只要檢查6n + 1與6n + 5就可以了，也就是直接跳過2與3的倍

數(shù)，使得程式中的if的檢查動作可以減少

源碼實現(xiàn)