初学者：Python——求规定数值以内、求是否有素数（质数）代码详解_输出素数python代码

首先，介绍一个素数的概念

素数也叫质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

我们小的时候一直背：
二三五七一十一 一三一九一十七 等等
即2 3 5 7 11 13 19 17等
这些数其实都是素数
每个数字都有一个特点，即：这个数字只能被1和它本身的数字整除
其实记住上面这句话，就可以开始做编程了。

我们先不定义范围内素数的输出，我们这里先判断一下某个数字是否是素数。
怎么判断呢，暴力法将解决任何问题。
我们可以通过穷举的方式判断一个数是否是素数。
比如说，18是素数吗？
按照定义，除了1和18两个数字以外，还有没有哪个数字能够将18整除？如果有，那么它就不是素数，反之则是。代码如下：

def isPrime(x):
    # 判断x是否是素数
    flag = True  # 默认情况下x是素数
    if x <= 1:
        flag = False
        print("我们认为小于1的数不算素数")
    else:
        for i in range(2, x):
        	# 在这个for中，我们遍历2-x中的所有数字，如果有能被整除的，则说明还有其他数字能整除x，返回不是素数。
        	# 举例：判断数字8是否是素数，我通过穷举，除了1和8，即2-7中是否存在数字a，x除以a取余为0，若有，说明不是素数。
            if x % i == 0:
                flag = False
    return flag


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

接下来，我们来通过以下具体方法，来介绍如何输出所有范围内的素数。
我们默认只输入一个值x，意思为输出所有1-x中的素数。

1.暴力法（穷举）

如果要通过该法实现输出所有的素数，需要通过两重for来实现，具体代码如下：

def isPrime(x):
    # 判断x是否是素数
    flag = True  # 默认情况下x是素数
    if x <= 1:
        flag = False
        print("我们认为小于1的数不算素数")
    else:
        for i in range(2, x):
            if x % i == 0:
                flag = False
    return flag

def OutputPrime(x):
    """
    :param x: 传入参数x
    1.x范围内的所有数字。由于我们找素数，我偷懒直接从2开始了。 假如我找2-10之内的所有素数，首先先遍历一遍所有数字
    2.再来一重for循环，目的是为了判断这个数字是否是素数。判断方式就是判断素数的函数isPrime
    """
    for i in range(2, x + 1):
        if isPrime(i):
            print(i, end=" ")


n = int(input())

OutputPrime(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

但是呢，用这种办法有个很严重的问题，就是当x很大的时候，就很麻烦了，我们可以通过查看计算次数和运行时间来判断这段代码：
首先，大家把自己的代码去试一下，测一下运行时长，通过这个：

start = time.perf_counter()
# 你自己的代码块，主要是for语句
end = time.perf_counter()
print(" ")
print('运行时间为：{}秒'.format(end-start))
1
2
3
4
5

我输入了10万次，运行结果为：

print('运行时间为：{}秒'.format(end-start))
# 运行时间为：295.7721692秒
1
2

很明显，这个时间也太长了，如果数字一大，就很崩溃
所以，我们看一下有没有什么优化方法：

2.使用开方的方式将范围缩短

为什么用开方呢，其实如果一个数能被除了1和本身的数整除，那么就说明这个数一定能被其中某两个数相乘。
举例子：
36。这个数能被1 2 3 4 6 9 12 18 36整除。
64。这个数能被1 2 4 8 16 32 64整除。
也就是说，被拆分的数字一定有一个数字在1-6（1-8）之间
因此，如果在2-6中找不到能被整除的数，则肯定后面都没有。
因此，只需要修改判断素数。代码如下：

def isPrime(x):
    # 判断x是否是素数
    flag = True  # 默认情况下x是素数
    if x <= 1:
        flag = False
        print("我们认为小于1的数不算素数")
    else:
        for i in range(2, int(x ** 1/2) + 1):
            if x % i == 0:
                flag = False
    return flag
1
2
3
4
5
6
7
8
9
10
11

根号的方式大家自行选择，可以math.sqrt()或者pow()。均可
运行后时间如下：

# 运行时间为：117.3293237秒
1

缩短了一倍多，很不错了。再看看

3.去偶数法

观察所有的素数，你会发现，除了2以外的所有的素数都是奇数。所以，2特判，然后跳过偶数去找奇数里面的素数，范围直接又缩小了一半。代码：

def OutputPrime(x):
    print("2", end=" ")
    for i in range(1, x + 1, 2):
        if i == 1:
            continue
        elif isPrime(i):
            print(i, end=" ")
1
2
3
4
5
6
7

运行时间：

# 运行时间为：59.0722829秒
1

4.素数的性质

所有大于3的素数，只有6n-1和6n+1。证明过程省略，我给编程：

# 5 7 11 13 17 19 23 29 31 37
n = int(input())
x = 7
s = 4
p = [2, 3, 5]  # 提前把2 3 5放进来
while x < n:  # 当前的x不超过输入的数字n
    if x % 5 != 0:
        r = int(x ** 0.5) + 1  # 此处使用前面的方法2
        for i in range(3, r, 2):
            if x % i == 0:
                break
        else:  # 如果上面的for循环正常执行，则不会执行该else
            p.append(x)
    x += s
    s = 4 if s == 2 else 2

print(p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最后分享大佬写的代码，真离谱：

# 生成小于10w的所有质数的列表
prime_numbers = []

# 遍历范围在2到1000000之间的数字
for n in range(2, 1000000):
    # 判断是否为质数的条件
    is_prime = all(n % i != 0 for i in range(2, int(n ** (1/2)) + 1))
    # 如果是质数，则添加到列表中
    if is_prime:
        prime_numbers.append(n)

# 打印结果
print(prime_numbers)
1
2
3
4
5
6
7
8
9
10
11
12
13

这个代码跑的时间为：

# 运行时间为：6.1031375秒
1

大家自行体会吧！！！
共勉！