埃拉托斯特尼篩法，簡稱埃氏篩，一種古老且簡單的用來找出一定范圍內(nèi)所有的質(zhì)數(shù)的算法。公元前250年由希臘數(shù)學家埃拉托斯特尼提出

abstract.png

算法原理

判斷自然數(shù)n以內(nèi)的全部質(zhì)數(shù)，將不大于 的所有質(zhì)數(shù)的倍數(shù)剔除，剩下的即為該自然數(shù)n以內(nèi)的所有質(zhì)數(shù)

Step 1. 先設定整個序列，均標記為質(zhì)數(shù)

Step 2. 取出整個序列的第一個質(zhì)數(shù) P，此時為 2

Step 3. 將該質(zhì)數(shù)在n以內(nèi)的倍數(shù)全部標記為非質(zhì)數(shù)

Step 4. 根據(jù)標記信息按序取該序列中下一個質(zhì)數(shù)Q（此時為3），先判斷其平方值是否超過n，如果是，則該算法結(jié)束，質(zhì)數(shù)與否標記完成；否則，返回Step 3

Java實現(xiàn)

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int num = 0;
    for(int i=2; i<n; i++)
    {
        if(!notPrime[i])
        {       
            num++;
            for(int j = 2; i*j < n; j++)    // 將該質(zhì)數(shù)的倍數(shù)標記為非質(zhì)數(shù)
            {
                notPrime[i*j] = true;
            }
        }
    }
    return num;
}

Note

之前筆者在解決該問題是對n以內(nèi)所有數(shù)依次進行質(zhì)數(shù)判斷，結(jié)果發(fā)現(xiàn)費時費力…………

不得不感嘆，古人的智慧是無窮的鴨…………