Python 输出指定范围内的素数

素数（prime number）又称质数，有无限个。除了1和它本身以外不再被其他的除数整除。

以下实例可以输出指定范围内的素数：

实例(Python 3.0+)

#!/usr/bin/python3 # 输出指定范围内的素数 # take input from the user lower = int(input("输入区间最小值: ")) upper = int(input("输入区间最大值: ")) for num in range(lower,upper + 1): # 素数大于 1 if num > 1: for i in range(2,num): if (num % i) == 0: break else: print(num)

执行以上程序，输出结果为：

$ python3 test.py 
输入区间最小值: 1
输入区间最大值: 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

使用试除法

试除法是一种基本的算法，它对每个数进行除法测试以判断是否为素数。以下是使用试除法输出指定范围内素数的代码：

实例

def is_prime(n):
"""判断一个数是否为素数"""
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True

def primes_in_range(start, end):
"""输出指定范围内的素数"""
for num in range(start, end + 1):
if is_prime(num):
print(num)

# 示例：输出 10 到 50 范围内的素数
primes_in_range(10, 50)

使用埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更高效的算法，尤其适用于找出较大范围内的素数。以下是使用埃拉托斯特尼筛法输出指定范围内素数的代码：

实例

def sieve_of_eratosthenes(max_num):
"""使用埃拉托斯特尼筛法找出 max_num 以内的所有素数"""
sieve = [True] * (max_num + 1)
sieve[0] = sieve[1] = False # 0 和 1 不是素数
p = 2
while p * p <= max_num:
if sieve[p]:
for multiple in range(p * p, max_num + 1, p):
sieve[multiple] = False
p += 1
return [p for p, is_prime in enumerate(sieve) if is_prime]

def primes_in_range(start, end):
"""输出指定范围内的素数"""
primes = sieve_of_eratosthenes(end)
for num in primes:
if num >= start:
print(num)

# 示例：输出 10 到 50 范围内的素数
primes_in_range(10, 50)

Document 对象参考手册 Python3 实例

返回顶部

菜鸟教程

Python 输出指定范围内的素数

实例(Python 3.0+)

使用试除法

实例

使用埃拉托斯特尼筛法

实例