Проверка на простоту
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
bool prime(long long n){
for(long long i=2;i<=sqrt(n);i++)
if(n%i==0)
return false;
return true;
}
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма:
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
bool ferma(long long x){
if(x == 2)
return true;
srand(time(NULL));
for(int i=0;i<100;i++){
long long a = (rand() % (x - 2)) + 2;
if (gcd(a, x) != 1)
return false;
if( pows(a, x-1, x) != 1)
return false;
}
return true;
}
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
long long gcd(long long a, long long b){
if(b==0)
return a;
return gcd(b, a%b);
}
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
long long mul(long long a, long long b, long long m){
if(b==1)
return a;
if(b%2==0){
long long t = mul(a, b/2, m);
return (2 * t) % m;
}
return (mul(a, b-1, m) + a) % m;
}
long long pows(long long a, long long b, long long m){
if(b==0)
return 1;
if(b%2==0){
long long t = pows(a, b/2, m);
return mul(t , t, m) % m;
}
return ( mul(pows(a, b-1, m) , a, m)) % m;
}
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Асимптотика решения
Итоговая асимптотика проверки на простоту — O (K * log N * log N), где K — количество итераций теста Ферма, которое обычно равняется 100. Если требуется проверить на простоту число типа int, то можно обойтись без двоичного умножения. Тогда асимптотика проверки на простоту будет равна O (K * log N).
