Python: вывод простых чисел в заданном диапазоне
Python3 ПримерыПростые числа бесконечны. Кроме 1 и самих себя, они не делятся ни на какой другой делитель.
Следующий пример выводит простые числа в заданном диапазоне:
Пример (Python 3.0+)
#!/usr/bin/python3
# Вывод простых чисел в заданном диапазоне
# получение ввода от пользователя
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)
Другие расширения