Алгоритм проверки на простоту за O (log N)
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма: 
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Простое число
Данный калькулятор поможет проверить — является ли заданное число простым. Интерактивная таблица малых и больших простых чисел.
Определение: Простое число — это натуральное число (>0), которое имеет не более двух различных делителей: 1 и само число.
Натуральные числа, кроме 1, не относящиеся к простым числам, называются составными.
Единица не является ни простым числом ,ни составным.
Примеры простых чисел: 3,5,7,11,17
Возьмем, к примеру, число 3. 3 делится ,нацело, только на 1 и само на себя, следовательно число 3 является простым числом.
Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включенное в этот набор. Противоречие.
Взаимно математики предлагали другие доказательства. Одно из них (приведенное Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растет с ростом n.
Простые числа
Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x. К примеру, 5 — простое число, а 6 является составным числом, так как, помимо 1 и 6, также делится на 2 и на 3.
Данных онлайн калькулятор позволяет выполнить следующие операции:
- Проверить является ли число простым или составным.
- Сгенерировать последовательность простых чисел до заданного числа.
- Сгенерировать последовательность из N простых чисел, где N — заданное пользователем число.
Онлайн калькуляторы
Calculatorium.ru — это бесплатные онлайн калькуляторы для самых разнообразных целей: математические калькуляторы, калькуляторы даты и времени, здоровья, финансов. Инструменты для работы с текстом. Конвертеры. Удобное решение различных задач — в учебе, работе, быту.
Актуальная информация
Помимо онлайн калькуляторов, сайт также предоставляет актуальную информацию по курсам валют и криптовалют, заторах на дорогах, праздниках и значимых событиях, случившихся в этот день. Информация из официальных источников, постоянное обновление.