求小于n的质数的个数——埃拉托斯特尼筛法

Contents
  1. 问题描述
  2. 算法描述

问题描述

给定一个非负数n,求小于n的质数的个数。

算法描述

在本题中,我们采用埃拉托斯特尼筛法,详细列出算法如下:

  1. 从2开始遍历到根号n;
  2. 先找到第一个质数2,然后将其所有的倍数全部标记出来;
  3. 然后到下一个质数3,标记其所有倍数,依次类推,直到根号n;
  4. 此时数组中未被标记的数字就是质数。

效果图如下:

Sieve_of_Eratosthenes_animation

下面给出ruby和python代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
!#/usr/bin/ruby
# @param {Integer} n
# @return {Integer}
def count_primes(n)
return 0 if n < 2
mark = [true] * n
mark[0], mark[1] = false, false
2.upto(Math.sqrt(n)) do |i|
if mark[i]
p = i ** 2
while p < n
mark[p] = false
p += x
end
end
end
mark.count(true)
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
!#/usr/bin/python
def _odd_iter():
n=1
while True:
n = n + 2
yield n
def _not_divisible(n):
return lambda x : x % n > 0
def primes():
yield 2
it = _odd_iter()
while True:
n=next(it)
yield n
it = filter(_not_divisible(n), it)
for n in primes():
if n < 1000:
print(n)
else:
break