Простые числа очень важны. Большая часть современной расшифровки шифрования в значительной степени зависит от этих простых чисел. Таким образом, генерация этих простых чисел сама по себе является хорошей задачей.
В этой статье мы увидим, как мы можем сгенерировать список простых чисел, используя решето Эратосфена.
Что такое сито Эратосфена?
Чтобы найти все простые числа, меньшие или равные 20, выполните следующие действия.
Сначала сгенерируйте список целых чисел от 2 до 20:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Первое число в списке — 2. Удалите из списка все числа, которые делятся на 2.
2 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 *
Повторите тот же процесс со следующим номером и пропустите номер, который удален.
2 3 * 5 * 7 * * * 11 * 13 * 15 * 17 * 19 *
Следующее еще не вычеркнутое число в списке после 3 — 5. Вычеркните все числа, кратные 5.
2 3 * 5 * 7 * * * 11 * 13 * * * 17 * 19 *
Следующим еще не вычеркнутым числом в списке после 5 является 7. Следующим шагом будет вычеркивание каждого 7-го числа в списке после 7, но они все уже вычеркнуты в этот момент, так как эти числа (14) также кратны меньшим простым числам, потому что 7 × 7 больше 20. Числа, не вычеркнутые в этой точке списка, — это все простые числа меньше 20.
2 3 5 7 11 13 17 19
Здесь вы получаете список простых чисел меньше 20.
Реализация на Python
def sieve(n):
primes=[]
temp_list = [0 for x in range(0,n)]
i,j=2,2
while(i*j<n):
temp_list[i*j] = 1
j=j+1
if i*j >= n:
i,j = i+1,2
for i in range(2,n):
if temp_list[i] == 0:
primes.append(i)
return primes
if __name__ == '__main__':
n = int(input())
print sieve(n)
Входные данные для этого будут такими:
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]
Теперь давайте обсудим нашу реализацию.
Что мы сделали, так это использовали индексы, и вместо того, чтобы пересекать значения, мы поставили 1 в этих индексах, чтобы они отличались как непростые.
Мы берем список длиной n, заполняем его 0, а затем переходим к 4-му индексу, помечаем его 1, затем к 6, затем 8-му индексу и помечаем их 1 так же, как мы делали при скрещивании чисел. Затем то же самое с 3 , 5 и так далее.
Мы берем список, как показано ниже.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
На следующем шаге мы помечаем все значения индексов, деленные на 2, как 1.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
На следующем шаге мы помечаем все значения индексов, деленные на 3, как 1.
0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Теперь отметьте все значения индексов, деленные на 5, как 1.
0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Все индексы, у которых осталось значение 0, являются простыми числами.
2 3 5 7 11 13 17 19
Это все простые числа.
Вот как вы создаете список простых чисел, используя метод сита в python. Если вам понравилась статья, поделитесь ею и подпишитесь.
Первоначально опубликовано на www.learnsteps.com 24 августа 2018 г.
