素数问题

问题描述

判断一个数是否为素数

解决方案

一般方法
算法第4版p13中提到
判断2到根号n内的数

#只用判断n是否能被2到根号n整除，是则返回True，反之返回False
def isPrime1(n):
    for i in range(int(math.sqrt(n)))[1:]:
        if n%i==0:
            return True
    return False

埃氏筛法
摘抄一段 具体见此
首先，列出从2开始的所有自然数，构造一个序列：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取序列的第一个数2，它一定是素数，然后用2把序列的2的倍数筛掉：

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取新序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取新序列的第一个数5，然后用5把序列的5的倍数筛掉：

7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

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

#埃氏筛法
def _odd_iter(n):
    i=1
    while i<n:
        i=i+2
        yield i

def _not_divisible(i):
    return lambda n: True if n==i else n%i>0

def isPrime2(n):
    t=list(_odd_iter(n))
    for j in t:
        t=list(filter(_not_divisible(j),t))
        print(t)
    return t[len(t)-1]==n