Итак, давайте начнем с определения того, что такое простое число. Это целые числа, не имеющие других делителей, кроме самих себя. Теперь, что такое тестирование Primality? Это так же просто, как определить простое число — решить, является ли значение простым числом.

Наивное тестирование простоты

Простая реализация проверки простоты, в которой мы проверяем, делится ли любое значение, меньшее числа, нацело. Но этот метод будет неэффективен для больших чисел. Итак, сначала давайте начнем с уменьшения количества сделанных тестов.

Теперь давайте начнем с нахождения множителей заданного числа «n». Самый простой способ найти множитель — извлечь квадратный корень из числа.

sqrt(n) = p, поэтому мы получаем один фактор «p».

Теперь, если мы умножим «p» само на себя, мы получим «n».

п * п знак равно п . Это также можно записать как a * b = n, где «a» и «b» — два множителя «n».

Теперь, если «а» увеличивается, «b» должно уменьшаться, чтобы сохранить a * b = n. Таким образом, по крайней мере один множитель должен быть меньше или равен квадратному корню из «n», и если мы не можем найти какой-либо множитель ‹ или = для sqrt (n), тогда «n» должно быть простым.

Таким образом, мы сократили количество итераций.

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

Таким образом, мы можем оптимизировать его, но за счет места.

Сито Эратосфена

Решето Эратосфена — это простой древний алгоритм нахождения всех простых чисел до заданного предела.

Он делает это, итеративно помечая как составные (т. е. не простые) числа, кратные каждому простому числу, начиная с первого простого числа, 2.

Рандомизированное тестирование Миллера-Рабина

Предположим, что n › 3 — нечетное число, и мы пишем n-1 = 2^s *d. Теорема утверждает, что «n» не является простым, если существует «a», такое что выполняются следующие уравнения.

Это вероятностный алгоритм. Мы можем уменьшить ошибку за счет увеличения времени выполнения, запустив тест несколько раз.

Надеюсь, вы найдете эту статью полезной. В № 2 мы рассмотрим реализации вышеуказанных алгоритмов.