9.1-质数多种解法及效率

素数问题

求100以内的素数（25个）
1.一个数能被从2开始到自己的平方根的正整数整除，就是合数；
2.一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果被一个素数
整除就是合数；
3.质数定理：大于3的素数只有6N-1和6N+1 两种形式；

#素数问题

import math
n=100
for x in range(2,n):
    for i in range(2,math.ceil(math.sqrt(x))):
        if x%i == 0:
            break
    else:
        print(x)

方法2 去掉math函数部分；
#储存质数合数一定可以分解为几个质数的乘积；
n=100
lst=[2]
for i in range(3,n,2):    #
    for j in lst:  # (3,i**0.5+1,2)=lst
        if i%j==0:
            break
    else:
        print(i)  #找到了一个质数；
        lst.append(i)

#质数解法2：
n = 100
count = 1
primenubers=[]

for x in range(3,n,2):
    for i in range(3,int(x**0.5)+1,2):
        if x % i == 0:
            break
    else:
        count += 1
print(count)

方法3——改进方案；
n=100
lst=[2]
for i in range(3,n,2):    #
    flag=False
    for j in lst:  # (3,i**0.5+1,2)=lst
        if j>i**0.5:
            flag=True
            break
        if i%j==0:
            flag=False
            break  #合数
    if flag:
        print(i)  #找到了一个质数；
        lst.append(i)

几种优化策略