Доброго времени суток, товарищи!
Сегодня я продолжу речь про простые числа, а именно, расскажу про Решето Эратосфена.
Когда-то давным-давно древнегреческому математику Эратосфену Киренскому пришла в голову одна замечательная идея, который мы пользуемся и по сей день. Суть состоит в том, чтобы находить все простые числа до какого-то заданного n, вычеркиванием составных чисел.
*составное число - число, которое можно представить в виде с = a*b, где ни a ни b не являются 1*
Представим, что мы уже знаем, что 2 (первое простое число) - простое число. А что будет, если мы начнем домножать 2 на разные последовательные числа, отличные от 1? Мы однозначно получим числа, которые быть простыми не могут, ведь у нас число будет иметь как минимум 2 делителя отличные от 1 и самого числа(2 и то число, на которое мы домножим). Посмотрим на примере: 2 - простое, но числа 2*2, 2*3, 2*4 ... 2*k (2*k <= n, напомню, что мы ищем числа до заданного n) - не простые. Теперь мы просто возьмем и вычеркнем их из ряда всех чисел до n, ведь мы знаем, что они не простые.
Теперь возьмем следующее число в ряде. Может ли оно быть составным? Нет, потому что мы вычеркнули все числа, составленные из 2. Получается, что следующее число не составлено из 2, но кроме 2 ему не из чего быть составленным, так как мы берем следующее минимальное невычеркнутое число. Получается, что следующее число не составное, то есть простое (это будет 3). Аналогично со всеми другими числами.
Это была сухая теория, я думаю на примере будет понятно куда проще.
Пусть задано число 21:
Изначально у нас есть ряд чисел:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 (без 1, так как 1 ни простое ни составное число)
Теперь вычеркиваем все числа, кратные 2:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
Следующее не вычеркнутое число - 3. Вычеркиваем все числа, кратные 3:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
Числа, кратные 5 вычеркнуты, числа, кратные 7 тоже, а чисел, кратных 11, 13, 17, 19 нет. Мы получили список простых чисел от 1 до 21:
2, 3, 5, 7, 11, 13, 17, 19.
Это довольно удобно, понятно, а главное - быстро!
Асимптотика O(n*log(log(n))).
Оптимизированное Решето Эратосфена.
Существуют несколько способов оптимизации:
1. Можно уменьшить количество проводимых операций, без улучшения асимптотики: будем просто просеивать простыми до корня из n. Числа, идущие после корня из n будут однозначно простыми.
2. Следующее улучшение мы можем провести, зная, что все четные числа будут однозначно не простыми (кроме 2), поэтому мы будем вычеркивать числа по нечетным, никак не храня четные числа (вдвое сокращает память и количество операций).
Суть работы:
У нас есть массив чисел: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25.
Можно заметить, что все числа, кратные 3 будут стоять через 2 числа после 3, числа, кратные 5 - через 4 и так далее.
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25; - уходят все, кратные 3.
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25; - уходят все, кратные 5.
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 - уходят все, кратные 7.
Далее остаются только простые числа: 3, 5, 7, 11, 13, 17, 19, 23.
В следующих статьях мы поговорим о блочном и линейном Решетах Эратосфена, дабы не перегружать одну статью информацией.