Некоторые алгоритмы, которые используются для проверки числа на простоту:

• Переборка делителей. 14 Определяет простоту числа методом полного перебора любых потенциально вероятных делителей. 1 На практике в исходном варианте не применяется, так как требует больших вычислительных мощностей. 1
• Метод Вильсона. 1 Относится к первой группе алгоритмов, даёт возможность сказать, простое число или составное. 1
• Алгоритм Поклингтона. 1 Относится к первой группе, находит применение при нахождении простых чисел значительных размеров. 1
• Алгоритм Ферма. 12 Вероятностный метод, основанный на малой теореме Ферма. 2 Не даёт гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. 2
• Алгоритм Миллера-Рабина. 12 Вероятностный тест, который позволяет с высокой точностью определить простоту числа, особенно для больших чисел. 2