Простые числа: как их находить?
Многие задачи ЕГЭ требуют либо находить простые числа, либо проверять их на простоту. В этой статье мы рассмотрим, как быстро проверять, является ли данное число простым, а также находить простые числа.
Метод "грубой силы": просто, но медленно
Если чисел немного и они на слишком велики, то вполне годится "метод грубой силы": пробуем делить наше число на все числа меньше его. Если не найдется чисел, на которые наше число делится без остатка, то оно простое.
Приведем фрагмент программы, который осуществляет проверку числа n:
prime = True
for i in range(2,n):
if n%i == 0:
prime = False
break
По завершении цикла переменная prime будет иметь значение True, если число n простое, и False в противном случае.
Процедуру можно существенно ускорить, если проверять делимость на числа в диапазоне от 2 до квадратного корня из проверяемого числа. Можно также отдельно проверить делимость на 2, а потом - только на нечетные числа.
Улучшенный код выглядит так:
prime = True
if n%2 == 0 and n > 3:
prime = False
else:
i=3;
while i*i <= n:
if n%i == 0:
prime = False
break
i += 2
Второй вариант работает гораздо быстрее. Например, для проверки на простоту чисел от 2 до 100000 первому варианту потребовалось около 38 секунд, а второму - всего 0,35 секунды. Поэтому второй вариант - вполне рабочий.
Однако гораздо быстрее проверять делимость не на все нечетные числа, а только на простые. Но для этого необходимо предварительно создать массив, содержащий простые числа.
Как составить таблицу простых чисел?
Программа составления массива простых чисел не так уж и сложна. Приведем соответствующий фрагмент кода.
limit = 1000000
primes=[2]
for n in range(3,limit+1,2):
k=0
prime = True
while primes[k]*primes[k] <= n:
if n%primes[k] == 0:
prime = False
break
k += 1
if prime: primes.append(n)
В переменной limit задается верхний предел поиска простых чисел: после завершения в массив primes будут помещены все простые числа, не превосходящие значение limit.
Вначале помещаем в массив primes число 2 - единственное четное простое число. В дальнейшем будем проверять лишь нечетные числа. Это делается в цикле, в котором переменная n принимает все нечетные значения, начиная с трех и не превосходящие заданного предела. Для каждого нечетного числа проверяется его делимость на все найденные ранее простые числа, не превосходящие корня из данного числа. Если проверяемое число разделится на какое-либо из простых чисел без остатка, то это число - составное. В противном случае число - простое, оно добавляется в массив primes.
Программа работает достаточно быстро: все простые числа, не превосходящие миллиона, находятся примерно за 5 секунд.
(c) Ю.Д.Красильников, 2021 г.
Комментарии
Отправить комментарий