Предельное число

Как найти маленькие простые числа

Существует простой метод нахождения списка простых чисел. Его создал Эратосфен. Он носит название "Решето Эратосфена". Оно отлавливает числа, которые не являются простыми (как сито), и пропускает простые числа.

Метод работает со списком чисел и специальным числом b, которое изменяется в ходе метода. По мере выполнения метода вы обводите некоторые числа в списке и вычеркиваете другие. Каждое обведенное число является простым, а каждое вычеркнутое - составным. В самом начале все числа простые: не обведены и не зачеркнуты.

Метод всегда один и тот же:

1. На листе бумаги напишите все целые числа от 2 до проверяемого числа. Не записывайте число 1. Перейдите к следующему шагу.
2. Начните с b, равного 2. Перейдите к следующему шагу.
3. Обведите кружком b в списке. Перейдите к следующему шагу.
4. Начиная с b, отсчитайте еще b чисел в списке и вычеркните это число. Повторяйте отсчет еще b чисел и вычеркивание чисел до конца списка. Перейдите к следующему шагу.
• (Например: Когда b равно 2, вы обводите 2 и вычеркиваете 4, 6, 8 и так далее. Когда b равно 3, вы обводите 3 и вычеркиваете 6, 9, 12 и так далее. 6 и 12 уже были вычеркнуты. Вычеркните их снова).
5. Увеличьте b на 1. Перейдите к следующему шагу.
6. Если b было вычеркнуто, вернитесь к предыдущему шагу. Если b - это номер в списке, который не был вычеркнут, перейдите к третьему шагу. Если b нет в списке, перейдите к последнему шагу.
7. (Это последний шаг). Вы закончили. Все простые числа обведены кружком, а все составные числа зачеркнуты.

В качестве примера вы можете использовать этот метод на списке чисел от 2 до 10. В конце будут обведены числа 2, 3, 5 и 7. Это простые числа. 4, 6, 8, 9 и 10 будут вычеркнуты. Это составные числа.

Этот метод или алгоритм занимает слишком много времени для поиска очень больших простых чисел. Но он менее сложен, чем методы, используемые для поиска очень больших простых чисел, такие как тест на первичность Ферма (тест, позволяющий определить, является ли число простым или нет) или тест на первичность Миллера-Рабина.

Для чего используются простые числа

Прайм-числа очень важны в математике и информатике. Ниже приведены некоторые реальные примеры их использования. Очень длинные числа трудно поддаются решению. Трудно найти их простые коэффициенты, поэтому чаще всего для шифрования и секретных кодов используются числа, которые, вероятно, являются простыми.

• У большинства людей есть банковская карта, по которой они могут получать деньги со своего счета, используя банкомат. Эта карта защищена секретным кодом доступа. Поскольку код необходимо сохранить в тайне, его нельзя хранить на карте в открытом виде. Для хранения кода в тайне используется шифрование. При шифровании используются умножение, деление и нахождение остатков больших простых чисел. На практике часто используется алгоритм под названием RSA. Он использует китайскую теорему об остатках.

• Если у кого-то есть цифровая подпись для электронной почты, используется шифрование. Это гарантирует, что никто не сможет подделать электронное письмо. Перед подписанием создается хэш-значение сообщения. Затем оно объединяется с цифровой подписью, чтобы получить подписанное сообщение. Используются примерно те же методы, что и в первом случае.

• Поиск самого большого простого числа, известного на сегодняшний день, стал своего рода спортом. Проверить, является ли число простым, может быть сложно, если число большое. Самые большие простые числа, известные в любое время, обычно являются числами Мерсенна, потому что самый быстрый известный тест на простоту - это тест Лукаса-Лехмера, который опирается на специальную форму чисел Мерсенна. Группа, которая занимается поиском простых чисел Мерсенна, находится здесь[1].