Python如何求质数？(输出200以内的质数)

🍄 法一：试除法

def is_prime(n):
    for j in range(2,int(n**0.5)+1): #也可用math.sqrt(n)
        if n%j == 0:
            return False
    return True

li = []
for i in range(2,101): 
    if is_prime(i):
        li.append(str(i))

print(' '.join(li))

🏈 法一改进版

import math

li = [2,3,5]
i = 5
gap = 2

def is_prime(n):
    j = 0
    while li[j] <= math.sqrt(n):
        if i % li[j] == 0:
            return False
        j += 1
    return True

while i <= 200:
    i += gap
    gap = 6 - gap
    if is_prime(i):
        li.append(str(i))

print("Total: " + str(len(li)))
print(' '.join(li))

🎉 法二：filter筛法

a = [i for i in range(2,101)]
b = []
while a:
    b.append(str(a[0]))
    a = list(filter(lambda x: x % a[0] != 0, a)) #这里使用了filter()方法,返回的不是列表,而是迭代器对象
print(' '.join(b))

注：这是采用了埃拉托斯特尼筛法

埃拉托斯特尼筛法；使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。——维基百科