python实现基于埃拉托斯特尼筛法快速生成素数的优化

埃拉托斯特尼筛法, 快速生成素数, 生成器方法生成超大字典

0x00 埃拉托斯特尼筛法

埃拉托斯特尼筛法，也就是我们常说的素数筛选法的一种方法：

0x02 优化

使用了python的生成器方法生成一个超大的字典，这样做的方法是为了减少内存的消耗，循环只需到n的平方根square_root就行了，然后测试一下，最大的8位数基本40s能求出所有质因子。用到一些小优化，在python 2 中while 1：要比while True：要快，if value：要比if value == True：，不相信的话可以测试一下，然后看一下它们生成的操作码，另外大数计算中最好不用for循环，而用while循环。

0x02 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python
# coding=utf-8
# author:admin[@hackfun.org]
# license:GPL v3
# blog:hackfun.org
def gen_super_dict(n):
    """use python generator to generate super dictionary and save memory"""
    i = 2 # 0 and 1 is not prime
    while 1:
        if i > n:
            break
        yield i
        i += 1
def gen_prime_list(n):
    """use prime screen method to generate all prime numbers less than n"""
    super_dict = {}
    primes_list = []
    for x in gen_super_dict(n):
        super_dict[x] = True
    i = 2
    while 1:
        if i > n:
            break
        j = i * i
        while 1:
            if j > n:
                break
            if super_dict[i]:
                super_dict[j] = False
            j += i
        i += 1
    for key,value in super_dict.items():
        if value:
            primes_list.append(key)
    return primes_list