isPrime

isPrime is a predicate used in mathematics and computer science to determine whether a given integer n is prime. By definition, a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Therefore isPrime(n) yields true if n is prime, and false otherwise. The function is defined for integers; for n <= 1 the result is false.

One common method, known as trial division, tests divisibility of n by integers from 2 up to floor(sqrt(n)). If any divides n, it is not prime; otherwise it is prime. Efficiency improvements include checking 2 separately, then testing only odd divisors, or using the 6k ± 1 optimization to skip numbers divisible by 2 or 3.

For large inputs, practical implementations use probabilistic primality tests such as Miller–Rabin, which can quickly declare a number composite with high probability and can be made deterministically correct for ranges of n by using a fixed set of bases. Deterministic tests exist but are less practical for general use; deterministic variants for specific ranges (such as 32-bit or 64-bit integers) provide guaranteed results.

In practice, isPrime is used in prime generation for cryptography, number theory research, and algorithms that require knowledge of primality. It underpins cryptographic key generation, primality proofs, and various algorithms that rely on primes.