Primality Test

To know if a number is prime, check if it has any divisor except 1 or itself, this test is called a primality test. The test first uses probabilistic algorithms and if the probability of being prime is non-zero, the algorithms become deterministic (careful verification of potential divisors).

Example: Is 23456789 a prime number ? True

Example: Is 123456789 a prime number ? False

It exists several test to know if a number is a prime number : Miller–Rabin or Lucas-Lehmer are the one used by dCode.

It is mainly a mathematical convention that avoids many problems in mathematical definitions and theorems (where one would have to exclude 1 or treat it as a special case). Another advantage is that the prime factor decomposition is unique 6 = 2*3 and not 1*2*3 or 1*1*1*2*3.

The deterministic algorithm tries all or almost all numbers (it avoids even numbers and multiples of 3). Here is a pseudo code applicable for prime numbers not too large: // pseudo-code
function is_prime(n) {
if n ≤ 1 return FALSE
else if n ≤ 3 return TRUE
else if (n mod 2 = 0) or (n mod 3 = 0) return FALSE
i = 5
while (i*i ≤ n) {
if (n mod i = 0) or (n mod (i + 2) = 0) return FALSE
i = i + 6
}
return TRUE