埃氏筛

埃拉托斯特尼筛法，简称埃氏筛，一种古老且简单的用来找出一定范围内所有的质数的算法。公元前250年由希腊数学家埃拉托斯特尼提出

算法原理

判断自然数n以内的全部质数，将不大于$\sqrt{n}$ 的所有质数的倍数剔除，剩下的即为该自然数n以内的所有质数

Step 1. 先设定整个序列$2,3,4,5, … , n-1$，均标记为质数

Step 2. 取出整个序列的第一个质数 P，此时为 2

Step 3. 将该质数在n以内的倍数全部标记为非质数

Step 4. 根据标记信息按序取该序列中下一个质数Q（此时为3），先判断其平方值是否超过n，如果是，则该算法结束，质数与否标记完成；否则，返回Step 3

Java实现

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++)	// 将该质数的倍数标记为非质数
            {
                notPrime[i*j] = true;
            }
        }
    }
    return num;
}

Note

之前笔者在解决该问题是对n以内所有数依次进行质数判断，结果发现费时费力…………

不得不感叹，古人的智慧是无穷的鸭…………