自己写的眼保程序(pynotify,pygtk)
求1/n的值里的循环数的循环长度(循环的位数)

筛选法求素数

dcy posted @ 2009年6月11日 09:38 in Python with tags 算法 , 4652 阅读

先给题目,就是我们要算num以内的素数之和,这里先给一个不是筛选法但是一句话能求得出的代码,不过效率就和筛选法差了N个等级

一句话代码(非筛选法):

 

  1. #!/usr/bin/env python
  2. import math
  3. print sum(p for p in xrange(2, 10000000) if 0 not in\
  4. [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.剩下的步骤就类似了。
筛选法代码:
  1. #!/usr/bin/env python
  2. import math
  3.  
  4. def sieve_method(num):
  5.     prime_data = [x for x in xrange(num + 1)]
  6.     for i in xrange(2,int(math.sqrt(num) + 1)):
  7.         if prime_data[i]:
  8.             start = i**2
  9.             step  = i
  10.             prime_data[start::step]=((num-start)/step + 1) * [0]
  11.     print sum(prime_data) -1#1 is not prime number
  12.  
  13. if __name__ == "__main__":
  14.     sieve_method(2000000)

在逛cocobear的blog无意中看到筛选法求素数

 

 

niu 说:
2009年10月05日 03:02

prime_data[start::step]=((num-start)/step + 1) * [0]
===========
这句没有看懂,特别是【0】是?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter