求素数的快速算法（python)
def primes(n):""" returns a list of prime numbers from 2 to < n """
if n < 2:return []
if n == 2: return
# do only odd numbers starting at 3
s = range(3, n, 2)
# n**0.5 may be slightly faster than math.sqrt(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s:
j = (m * m - 3)//2
s = 0
while j < half:
s = 0
j += m
i = i + 1
m = 2 * i + 3
# make exception for 2
return +
用这个算法求2000000以内的素数，2S都不用，够快的
页:
[1]