埃氏筛

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

abstract.png

算法原理

判断自然数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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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以内所有数依次进行质数判断,结果发现费时费力…………

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

0%