求素数的一个快速算法 Python 快速输出素数算法

思想

以 100 以内为例。

1. 生成一个全是 True 的 101 大小的数组
2. 2 开始，遇到2的倍数（4,6,8,10...）都赋值为 False
   

   因为这些数字都有 因子 2

3. 3 开始，遇到 3 的倍数（6,9,12...）都赋值为 False
   

   因为这些数字都有 因子 3

4. 以此类推，把所有数字的倍数都赋值为 False
5. 输出值是 True 的数组下标

代码

""" 求100以内的素数 """

n = 100

l1 = [True for i in range(n+1)]

for i in range(2,n+1):

    j=i+i

    while j<n:

        l1[j]=False

        j = j + i

print("素数：")

for i in range(2,n):

    if l1[i]==True:

        print(i,end=" ")

改进

此算法有几个缺点：

1. 除了 2 之外的偶数都是合数，因此，完全可以建 一半 大小的数组
2. 3 的倍数有 12 ， 6 的倍数也是 12 ， 这样两个的赋值就是重复的、无效的