Решето Эратосфена

Решето Эратосфена – это старейший из известных способов выписывания простых чисел.

Он не требует вычисления отдельных делителей, прост в программировании и находит все простые числа меньшие, чем определенная верхняя граница, но этот алгоритм неэффективен при поиске очень больших простых чисел, так как он требует уйму памяти и огромного количества итераций.

Ввод: нечетное натуральное n.

Вывод: список всех нечетных положительных простых чисел, меньших или равных n.

Шаг 1. Начинаем с создания вектора v с (n -1) / 2 ячейками, каждой из которых присвоено значение 1, и полагаем P = 3.

Шаг 2. Если P² > n, выписываем все числа 2j + 1, для которых значение j-й ячейки вектора равно 1 и останавливаемся; в противном случае переходим к шагу 3.

Шаг 3. Если значение ячейки вектора v с номером (P-1)/2 равно 0, увеличиваем P на 2 и возвращаемся к шагу 2; в противном случае переходим к шагу 4.

Шаг 4. Присваиваем новой переменной T значение P²; замещаем 0 значение ячейки вектора v c номером (T-1)/2 и увеличиваем T на 2P; повторяем эти два шага до тех пор, пока T<=n, затем увеличиваем P на 2 и возвращаемся к шагу 2.

Тест Люка – Лемера

Пусть p – простое число. Число Мерсенна М(p) является простым тогда и только тогда, когда S_p-2 mod M(p) = 0.

Главная составная часть теста – последовательность натуральных чисел: S₀, S₁, S₂, …, определяемая рекуррентной формулой

S₀ = 4 и S_k+1 = (S_k² –2) mod M(p).

Простые числа Мерсенна (M(p)=2^p-1, где p - простое):

Приложение 2. Разложение на множители