Python 求素数之多方法解析_python直接法算素数和筛选法的区别

素数简介：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
素数
1、素数的普通解法 直接上代码

import math
L=[2]
n=int(input("请输入所求素数的上限："))
for x in range(1,n):
    for i in range(2,x):
        if x%i==0:
            break
        else:
            pass
        #只需除到x的根号 挨着除完效率低
        if(i>math.sqrt(x)):  #if(i==x-1):   效果一样
            # print(x,",是一个素数")
            L.append(x)
            break
print(L)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这种方法求小一点的素数范围还行，如果数大一点就很慢了。比如输入n为1000000或者更大，上述方法效率就非常低了，运行时间太长。那怎么快速的求解呢，请看下面。

2、筛选法求解素数（埃拉托色尼筛选法）
具体原理：
计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：
首先，列出从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, …
不断筛下去，就可以得到所有的素数。

代码实现如下：

""" 求1000000以内的素数 """
n = 1000000
l1 = [True for i in range(n+1)]   #生成一个全是True的的数组
for i in range(2,n+1):            #2开始，遇到2的倍数（4,6,8,10...）都赋值为False
    j=i+i                         #3开始，遇到3的倍数（6,9,12...）都赋值为False
    while j<n:                    #以此类推，把所有数字的倍数都赋值为False
        l1[j]=False               #输出值是True的数组下标
        j = j + i
print("素数：")
T=[]
for i in range(2,n):
    if l1[i]==True:
        print(i,end=" ")
        T.append(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种方法就很快了，想知道时间的小伙伴，可以导入time模块算出运行时间，不会的就百度一下，这里就不赘述了。

以下还有几种筛选法的不同写法代码，效果一样

def countPrimes(n):
    """
    初始所有一个n维数组 res 表示数都为素数。
    从3开始将3的奇数倍标记成False，即不是素数。
    之后对每一个素数此行上一步操作
    这里我们不用管偶数倍，因为我们最后判定时默认所有偶数不是素数
    """
    if n < 3: return [2]
    res = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        res[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if res[i]]

print(countPrimes(1000000))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

i=int(input('please enter  an integer:'))
#创建一个空list
r=list()
#添加元素2
r.append(2)
#从3开始挨个筛选
for a in range(3,i):
    b=False
#用a除以小于a的质数b
    for b in r:
        if a % b == 0:
            b = False
            break
        else:
            b = True
    if b == True:
        r.append(a)
print(r)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def primes(n):
    if n < 2:  return []
    if n == 2: return [2]
    s = list(range(3, n, 2))
    mroot = n ** 0.5
    half = len(s)
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3) // 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2] + [x for x in s if x]
print(primes(1000000))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

谢谢点赞。