Jump to content

User talk:VictorGeere

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Simple Primality Test

[edit]

n is a prime if is not wholly divisible by n where

x = 1 when
x = 2 when
x = 3 when
...

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)


=
=

47784725839872000000/11 = 4344065985442909090.909090909

Therefore 11 is a prime.

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

Therefore 12 is not a prime.

Given the complexity of calculating the factorial of n-1 or even this algorithm is rather impractical except for its simplicity in testing the primality in the range of known factorials.