输出1-10000之间的质数python

一、法一：一个合数的所有因数最大的不会超过这个数的开方

a b = n ab=n ab=n
a < = s q r t ( n ) a<=sqrt(n) a<=sqrt(n)
b < = s q r t ( n ) b<=sqrt(n) b<=sqrt(n)

# # 1-10000里面的质数
import math
res = [2] # 保存结果
n = 10000
for i in range(3,n,2): # 2个步进，因为除了2所有的偶数都不会是素数
    flag = 1
    for j in range(2,math.floor(math.sqrt(i))+1):
        if i%j == 0:
            flag = 0 # 有能够被整除的了，所以不是素数
            break
    if flag: # 全程没有被整除
        res.append(i)
print(res)

二、法二：Eratosthenes筛（埃氏筛）

上图思想来自知乎大佬
翻译成python的代码如下：

is_prime = [None for i in range(10001)] #一个布尔数组
n = 10000
for i in range(2,n+1):
    is_prime[i] = True #假设这些都是素数
for i in range(2,n+1):
    for j in range(2*i,n+1,i): # j=2*i,j=3*i,j=4*i,....所以这些j肯定都不是素数
        is_prime[j] = False
res = []
for i in range(n+1):
    if is_prime[i] == True: #把最后保留下来的，加到结果里面
       res.append(i)
print(res)

三、法三：优化埃氏筛

优化一：每个合数必然有质因子，所以只用质数来筛除合数
优化二：缩小 i i i的范围，只到 s q r t ( n ) sqrt(n) sqrt(n),因为太大后面也没意义，因为最大的就是n
优化三： j j j 的初值变为 i ∗ i i*i i∗i
翻译成代码：

is_prime = [None for i in range(10001)] #一个布尔数组
n = 10000
for i in range(2,n+1):
    is_prime[i] = True #假设这些都是素数
for i in range(2,math.floor(math.sqrt(n))+1):
    if is_prime[i]: # 说明没有已经筛选过的合数
        for j in range(i*i,n+1,i): # j=2*i,j=3*i,j=4*i,....所以这些j肯定都不是素数
            is_prime[j] = False
res = []
for i in range(n+1):
    if is_prime[i] == True: #把最后保留下来的，加到结果里面
       res.append(i)
print(res)

不当之处，还望指正