VictorGeere

Simple Primality Test

n is a prime if $(n-1)!^{x}$ is not wholly divisible by n where

x = 1 when $2^{1}<=n<2^{2}$
x = 2 when $2^{2}<=n<2^{3}$
x = 3 when $2^{3}<=n<2^{4}$
...

This is because 4 is the smallest number to have two prime factors, 8 the smallest to have 3 prime factors, 16 the smallest to have 4 prime factors etc.

Prime is then easily tested for n = 11

(x = 3 because 2^3 <= 11 < 2^4)

$(11-1)!^{3}$
= $3628800^{3}$
= $47784725839872000000$

47784725839872000000/11 = 4344065985442909090.909090909

Therefore 11 is a prime.

To test the next integer (12), calculating the factorial becomes easier i.e.

$47784725839872000000*11^{3}/12=5300122507739136000000$

Therefore 12 is not a prime.

Given the complexity of calculating the factorial of n-1 or even $(\scriptstyle {}{\sqrt {n}})!$ this algorithm is rather impractical except for its simplicity in testing the primality in the range of known factorials.