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)
"""判断一个数是否为素数"""
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)
"""使用埃拉托斯特尼筛法找出 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)
hizmz
hiz***sina.com
与前面判断是否是质数一样,作者算法中未使用到"开根号法"来节约时间复杂度,同时为加入个数等说明,因此我对其改进如下:
hizmz
hiz***sina.com
Pt
idi***g@qq.com
先定义一个判断素数的函数,然后再输入范围去判断。
Pt
idi***g@qq.com
风林火山
dra***a_zby@163.com
风林火山
dra***a_zby@163.com
Transitive
276***1169@qq.com
在已经定于的数值中求所有的素数。
这个是求梅森素数的:
Transitive
276***1169@qq.com
vinson
wei***ng_vinson@163.com
修正重复输出质数的错误:
vinson
wei***ng_vinson@163.com
cc河豚
a12***4046@gmail.com
把版大的改造了下,增加平方根和只從質數判斷是否為質數,算大數字會快很多。
cc河豚
a12***4046@gmail.com
Kindred
268***8532@qq.com
hizmz真大佬,不过代码我研究了很久,还是给大佬加上注释如下,并对负数进行改进,如果需要,还可以自行添加对其他字符串进行限定输入。
Kindred
268***8532@qq.com
不是TheShy是Rookie
501***482@qq.com
更严谨的判断,更美观的输出:
输入 100 和 2 ,结果如下:
不是TheShy是Rookie
501***482@qq.com