User talk:VictorGeere

From Wikipedia, the free encyclopedia

[edit] Simple Primality Test

n is a prime if (n − 1)!x is not wholly divisible by n where

x = 1 when 21 < = n < 22
x = 2 when 22 < = n < 23
x = 3 when 23 < = n < 24
...

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
= 36288003
= 47784725839872000000

47784725839872000000/11 = 4344065985442909090.909090909

Therefore 11 is a prime.

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

47784725839872000000 * 113 / 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.