Математика и криптография
Проверка простых чисел
Введите число, чтобы узнать, простое ли оно и какое место занимает в упорядоченном списке простых чисел (2 — это #1).
Отлично подходит для быстрых проверок и развития интуиции. Лёгкие вычисления прямо в браузере, до 1 000 000.
Результат
История простых чисел
Простые числа — это строительные блоки целых чисел: они делятся только на 1 и на самих себя. Ещё более 2000 лет назад Евклид доказал, что простых чисел бесконечно много. Современная криптография (RSA, Diffie-Hellman, варианты ECC) опирается на свойства простых чисел для обеспечения безопасности.
Интересный факт: теорема о распределении простых чисел показывает, что простые числа редеют примерно как n / ln(n). Простые числа Мерсенна (2^p − 1, где p простое) встречаются редко и служат движущей силой таких проектов, как GIMPS, которые их ищут. Тесты на простоту теперь работают быстро (например, Миллера–Рабина, AKS), так что ответ на вопрос «простое ли это число?» получается почти мгновенно даже для огромных чисел.