Алгоритм нахождения простых чисел
Время на прочтение
3 мин
Количество просмотров 432K
Оптимизация алгоритма нахождения простых чисел
2 3 5 7 11 13 17 19 23 29 31… $250.000…
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1
# вводим N
n = input("n=")
# создаем пустой список для хранения простых чисел
lst = []
# в k будем хранить количество делителей
k = 0
# пробегаем все числа от 2 до N
for i in xrange(2, n+1):
# пробегаем все числа от 2 до текущего
for j in xrange(2, i):
# ищем количество делителей
if i % j == 0:
k = k + 1
# если делителей нет, добавляем число в список
if k == 0:
lst.append(i)
else:
k = 0
# выводим на экран список
print lst
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
# Листинг 2
n = input("n=")
lst = []
for i in xrange(2, n+1):
for j in xrange(2, i):
if i % j == 0:
# если делитель найден, число не простое.
break
else:
lst.append(i)
print lst
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
# Листинг 3
n = input("n=")
lst=[]
for i in xrange(2, n+1):
# пробегаем по списку (lst) простых чисел
for j in lst:
if i % j == 0:
break
else:
lst.append(i)
print lst
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
# Листинг 4
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
# Листинг 5
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
if (i > 10):
if (i%2==0) or (i%10==5):
continue
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
# Листинг 6
from math import sqrt
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
if (i > 10) and (i%10==5):
continue
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
# Листинг 7
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
if (i > 10) and (i%10==5):
continue
for j in lst:
if j*j-1 > i:
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Решето Эратосфена:
# Листинг 8
n = input("n=")
a = range(n+1)
a[1] = 0
lst = []
i = 2
while i <= n:
if a[i] != 0:
lst.append(a[i])
for j in xrange(i, n+1, i):
a[j] = 0
i += 1
print lst
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
The Sieve of Eratosthenes in two lines.
primes = set(range(2,1000000))
for n in [2]+range(3,1000000/2,2): primes -= set(range(2*n,1000000,n))
Edit: I’ve realized that the above is not a true Sieve of Eratosthenes because it filters on the set of odd numbers rather than the set of primes, making it unnecessarily slow. I’ve fixed that in the following version, and also included a number of common optimizations as pointed out in the comments.
primes = set([2] + range(3, 1000000, 2))
for n in range(3, int(1000000**0.5)+1, 2): primes -= set(range(n*n,1000000,2*n) if n in primes else [])
The first version is still shorter and does generate the proper result, even if it takes longer.
Разбор работы самой быстрой из известных мне реализаций решета Эратосфена на Vanilla Python, т.е. без использования дополнительных модулей.
(c) Bruno Astrolino E Silva — я лишь добавил отладочную информацию:
def primes(n, verbose=0):
""" Returns a list of primes < n """
# (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205
def pr(*args):
if verbose > 0:
print(*args)
sieve = [True] * n
pr("все чётные числа игнорируются и будут пропущены при возврате...n")
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
pr('содержимое решета:t{}'.format([x for x in range(3,n,2) if sieve[x]]))
pr(f'i:{i} вычёркиваем все числа кратные "{i}", начиная с "{i}^2": {list(range(i*i, n, 2*i))}')
sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
pr(f'sieve[{i}*{i}::2*{i}]=[False]*(({n-i}*{i-1})//(2*{i})+1)')
pr('содержимое решета:t{}'.format([x for x in range(3,n,2) if sieve[x]]))
pr('*' * 60)
return [2] + [i for i in range(3,n,2) if sieve[i]]
PS данная реализация очень эффетивно использует срезы и, благодаря этому, минимизирует число итераций цикла — в примере ниже для нахождения всех простых чисел меньше 50, понадобилось всего три итерации цикла.
Вывод для n=50:
In [165]: primes(50, verbose=1)
все чётные числа игнорируются и будут пропущены при возврате...
содержимое решета: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]
i:3 вычёркиваем все числа кратные "3", начиная с "3^2": [9, 15, 21, 27, 33, 39, 45]
sieve[3*3::2*3]=[False]*((47*2)//(2*3)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
************************************************************
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
i:5 вычёркиваем все числа кратные "5", начиная с "5^2": [25, 35, 45]
sieve[5*5::2*5]=[False]*((45*4)//(2*5)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]
************************************************************
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]
i:7 вычёркиваем все числа кратные "7", начиная с "7^2": [49]
sieve[7*7::2*7]=[False]*((43*6)//(2*7)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
************************************************************
Out[165]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.
Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).
Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:
- Шаг 1: Переберите все элементы в заданном диапазоне.
- Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
- Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
- Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
- Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.
Пример: код Python для печати простого числа в заданном интервале.
# First, we will take the input:
lower_value = int(input("Please, Enter the Lowest Range Value: "))
upper_value = int(input("Please, Enter the Upper Range Value: "))
print("The Prime Numbers in the range are: ")
for number in range(lower_value, upper_value + 1):
if number > 1:
for i in range(2, number):
if(number % i) == 0:
break
else:
print(number)
Выход:
Please, Enter the Lowest Range Value: 14 Please, Enter the Upper Range Value: 97 The Prime Numbers in the range are: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Заключение
В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.
Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.