python各种素数求法对比

版本1

最朴素的方法，对 2到n的每个数i，确认其是否能被从2到sqrt(i)的数整除

N = 10000 def isPrime(n): if n<=1: return False i = 2 while (i*i<=n): if n%i == 0: return False i+=1 return True prime_ls = [] for i in range(2,N): if isPrime(i): prime_ls.append(i)

版本2

对版本1的改进，排除掉i为偶数的情况

N = 10000 def isPrime(n): if n<=1: return False if n%2 == 0: return False i = 3 while (i*i<=n): if n%i == 0: return False i+=2 return True prime_ls = [2] for i in range(3,N): if isPrime(i): prime_ls.append(i)

版本3

网上最常见的python素数筛法，利用到了python的特性：生成器

N = 10000 def odd_iter(): n = 1 while(True): n += 2 yield n def not_divisble(n): return lambda x: x%n>0 def primes(): yield 2 it = odd_iter() while(True): n = next(it) yield n it = filter(not_divisble(n),it) prime_ls = [] for i in primes(): if i >= N: break prime_ls.append(i)

注：filter中的 not_divisble(n)，不能直接替代为 lambda x: x%n>0，原因未知

版本4

素数筛法

N = 10000 def get_primes(n): isp = [x%2==1 for x in range(n+1)] isp[1] = False isp[2]= True p = [2] for i in range(3,n+1,2): if(isp[i]): p.append(i) for j in p: if(i*j<=n): isp[i*j] = False else: break if(i%j == 0): break return p prime_ls = get_primes(N)

结果对比

表格中的数据为使用对应版本的算法，求小于N的所有素数所花时间的$mean\pm std$

方法N=1000N=5000N=10000N=50000版本1$604\mu s\pm 62.9\mu s$$6.23ms\pm 2.24ms$$11.8ms\pm 778\mu s$$108ms\pm 8.47ms$版本2$378\mu s\pm 49.2\mu s$$2.75ms\pm 230\mu s$$6.5ms\pm 276\mu s$$59.3ms\pm 9.29ms$版本3$1.64ms\pm 165\mu s$$23.3ms\pm 1.46ms$$81.8ms\pm 7ms$$1.4s\pm 66.6ms$版本4$224\mu s\pm 64.6\mu s$$1.03ms\pm 37.6\mu s$$2.07ms\pm 100\mu s$$11ms\pm 467\mu s$