筛选法求素数
先给题目，就是我们要算num以内的素数之和，这里先给一个不是筛选法但是一句话能求得出的代码，不过效率就和筛选法差了N个等级
一句话代码（非筛选法）：
-
#!/usr/bin/env python
-
import math
-
print sum(p for p in xrange(2, 10000000) if 0 not in\
-
[p % d for d in xrange(2, int(math.sqrt(p))+1)])
现在开始是筛选法：
原理大致如下：
若要求得16以内的所有素数，
1)在数组中存放一下数据：
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
2)
先筛选掉是2的倍数：
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
同理，继续筛选掉3的倍数.
当要筛选4的倍数的时候，由于4已经被筛选过了，所以4的倍数也必定筛选过了。因而跳过4,到5.剩下的步骤就类似了。
筛选法代码：
筛选法代码：
-
#!/usr/bin/env python
-
import math
-
-
def sieve_method(num):
-
prime_data = [x for x in xrange(num + 1)]
-
for i in xrange(2,int(math.sqrt(num) + 1)):
-
if prime_data[i]:
-
start = i**2
-
step = i
-
prime_data[start::step]=((num-start)/step + 1) * [0]
-
print sum(prime_data) -1#1 is not prime number
-
-
if __name__ == "__main__":
-
sieve_method(2000000)
在逛cocobear的blog无意中看到筛选法求素数
2009年10月05日 03:02
prime_data[start::step]=((num-start)/step + 1) * [0]
===========
这句没有看懂，特别是【0】是？