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