代码
比这篇新的文章:
用类快排的方法找寻"第n小"的数
比这篇旧的文章: theme
作者: 半瓶墨水, 点击736次, 评论(1), 收藏者(0)
打分:
所有评论，共1条：( 我也来说两句)
比这篇旧的文章: theme
筛法生成质数（素数）的生成器
语言: Python, 标签: 素数 质数 2008/06/30发布 4个月前更新作者: 半瓶墨水, 点击736次, 评论(1), 收藏者(0)
Python语言: 筛法生成质数（素数）的生成器
01 #!/usr/bin/python
02 # -*- coding: utf-8 -*-
03 # from: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/535154
04 import math
05
06 def gen_sieve(ceiling=None):
07 if ceiling is not None:
08 if ceiling % 2 == 0:
09 ceiling -= 1
10 highest_prime = math.ceil(math.sqrt(ceiling))
11 last_val = 1
12 found_primes = []
13 yield 2
14 while ceiling is None or ceiling > last_val:
15 current_val = None
16 while current_val is None:
17 current_val = last_val = last_val + 2
18 for prime, square in found_primes:
19 if current_val < square:
20 break
21 if current_val % prime == 0:
22 current_val = None
23 break
24 yield current_val
25 if ceiling is None or highest_prime > last_val:
26 found_primes.append((current_val, current_val ** 2))
27
28 def isprime(n):
29 for fac in gen_sieve(int(math.ceil(math.sqrt(n)))):
30 if n % fac == 0 and n != fac:
31 return fac
32 return 0
02 # -*- coding: utf-8 -*-
03 # from: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/535154
04 import math
05
06 def gen_sieve(ceiling=None):
07 if ceiling is not None:
08 if ceiling % 2 == 0:
09 ceiling -= 1
10 highest_prime = math.ceil(math.sqrt(ceiling))
11 last_val = 1
12 found_primes = []
13 yield 2
14 while ceiling is None or ceiling > last_val:
15 current_val = None
16 while current_val is None:
17 current_val = last_val = last_val + 2
18 for prime, square in found_primes:
19 if current_val < square:
20 break
21 if current_val % prime == 0:
22 current_val = None
23 break
24 yield current_val
25 if ceiling is None or highest_prime > last_val:
26 found_primes.append((current_val, current_val ** 2))
27
28 def isprime(n):
29 for fac in gen_sieve(int(math.ceil(math.sqrt(n)))):
30 if n % fac == 0 and n != fac:
31 return fac
32 return 0
所有评论，共1条：( 我也来说两句)
| 1 |
vilinov
1个月前
回复
还是用筛法比较快
|