Primes & Primality Testing

Test whether a number is prime using different algorithms. Compare trial division, Fermat's test, and Miller-Rabin test.

Input

Enter a positive integer ≥ 2

Algorithm Comparison
AlgorithmComplexityGuaranteesBest for
Trial DivisionO(√n)DeterministicSmall numbers
Fermat's TestO(k·log³n)ProbabilisticQuick screening
Miller-RabinO(k·log³n)ProbabilisticCryptography