Проверка на простоту

Чтобы определить, является ли данное число 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)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.

В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.

В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.