Вопрос определения того, является ли натуральное число N простым, известен как проблема простоты. Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число N, позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа N, то это число может являться простым с определенной вероятностью.

1.1. Пример работы

После некоторой оптимизации был исправлен баг вычисления корня длинной арифметикой, теперь можно извлечь корень любого сколь угодно большого числа в считанные миллисекунды. Цикл был оптимизирован, что дало прирост в скорости на 30%. К сожалению, быстрой скоростью алгоритм не обладает, по причине использования одного потока. Есть предположение, если использовать параллельные вычисления (многопоточность), то можно добиться лучшего результата.

Таблица результатов (пример с простыми числами)

1.2. Сложность алгоритма

Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. Худший случай, если перебор придется проводить от 2 до корня из n. Сложность данного алгоритма:

Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число p является простым, если оно больше 1 и при этом делится без остатка только на 1 и на p (на самого себя).

Пример: 5 простое число, потому что делится только на 1 и на 5, а 6 является составным числом, так как делится на 2 и 3, помимо 1 и 6.

Натуральные числа, бо́льшие единицы, не являющиеся простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один натуральный делитель), простые числа (имеющие два натуральных делителя) и составные числа (имеющие больше двух натуральных делителей). Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа являются элементарными «строительными блоками» натуральных чисел.

2.2. Тесты простоты

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Истинные тесты результатом вычислений всегда выдают факт простоты либо составности числа, вероятностный тест дает ответ о составности числа либо его несоставности с некоторой вероятностью. Если сказать проще, то вероятностный алгоритм говорит, что число скорее всего не является составным, однако в итоге оно может оказаться как простым, так и составным. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми.

На практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.

2.3. Дополнительная литература

Как проверить, является ли число простым

Список простых чисел