求1000以内的素数

算法问题逐渐成为面试题里的必考题目，但大多测试人员都对其不太重视，笔者也是如此，故决定开一个系列，不定期分享一些算法题目。今天来看一道经典的面试题，求1000内的素数。

素数定义：

除了1和它本身之外再不能被其他数整除的自然数。

##算法思想：

第一种解法 – 直接根据素数定义来，对于给定的数n，拿1～n-1的数去除n，只有n不能被任一个数整除，n才是素数。

def prime(n):
    for i in range(2, n): #1不是素数，所以循环从2开始
        if n%i ==0:
            return False
    return True
def get_prime(x):
    r_list = []
    for n in range(2, x+1): #1不是素数，所以循环从2开始， 求到x为止的素食，所以循环需要到x+1.
        if prime(n):
            r_list.append(n)
    return r_list
print((get_prime(1000))

看起来很简单对不对，但随着x的增大，时间复杂度开销太大了，有没有更好的方法呢？

对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数。我们一定要一个个的除过去吗？非也

对于一个自然数N，如果它不是素数，是合数，那么肯定存在1到N的两个数，n1×n2=N。那么n1 和n2不可能两个都大于根号n（√N），不难理解吧？我们可以把n1和n2看
成一对，假设n1 < √N，那么，只要n1能被N整除，N就不是素数。也就是说，只要2到√N之间的数能被N整除，那么N就不是素数，否则，N就是素数。

def prime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n%i ==0:
            return False
    return True
def get_prime(x):
    r_list = []
    for n in range(2, x+1):
        if prime(n):
            r_list.append(n)
    return r_list
print(len(get_prime(1000)))

对于每一个n, 查找范围是不是少了一半？我们再来想下。

除2之外的偶数，会不会是素数？不可能把，也就是说，偶数只有2是素数，那么素数之剩下奇数了，优化如下：

def prime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n%i ==0:
            return False
    return True
def get_prime(x):
    if x<2:
        return None
    if x ==2:
        return 2
    r_list = [2]
    for n in range(3, x+1, 2):
        if prime(n):
            r_list.append(n)
    return r_list
print(len(get_prime(1000)))

第二种解法 – 埃氏筛法.

列出从2开始的所有自然数，构造一个序列：2, 3, 4, 5, 6, 7, 8, 9, 10 …
取序列的第一个数2，它一定是素数，然后把序列的2的倍数筛掉, 剩下：3,5,7，9….
取新序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：5,7,….
取新序列的第一个数5，然后用5把序列的5的倍数筛掉：7…

不断筛下去，就可以得到所有的素数。

#以下代码摘抄自网络
def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n
def _not_divisible(n): #先别着急理解这个函数，看后面。
    return lambda x: x % n > 0  #此处>0可以更改为！=0.不影响结果，原因是要把所有可以被素数整除的数筛选掉。
def primes():
    yield 2
    it = _odd_iter() # 初始序列
    while True:
        n = next(it) # 返回序列的第一个数
        yield n
        it = filter(_not_divisible(n), it) # 构造新序列
		#难点在于理解这个_not_divisible函数里的x。filter函数用法是：filter(fuction,list)：将list中每一个元素带入到function中，计算返回值，将返回值为True的list中的元素形成一个新的list。
for n in primes():
    if n < 10:
        print(n)
    else:
        break