there is another way to test the primality of a no

There is another way to test the primality of a no.If n be any number then if (n-1)!+1 is divisible by n then n is a prime number

[akruppa]

Moved to Misc. Math.

Alex

[Jens K Andersen]

Originally Posted by shawn

if (n-1)!+1 is divisible by n then n is a prime number

Yes, and only if. This is Wilson's Theorem. It's computationally useless.

[ewmayer]

And the 2007 mfgoode Memorial Bronze Medal in Number Theory goes to the Thread Author, "For seminal work in the area of improved algorithmic efficiency in primality testing."

Shawn, PM me your snail-mail address and I'll send you your Medal, and even throw in a free handy-dandy neck-hanger thingie, "just like the Olympic athletes get."

I'm thinking we should award some MMBMNTs retroactively, seeing as the prize was only just established this year and the forum goes back a few years. Nominations for 2006? Bearnol, perhaps?

[Eivind]

Lest just make a quick and dirty survey.

This code

def f(n):
    a = 1
    for i in range (2,n+1):
        a = a*i
    return a

for i in range (2,3000):
    if (f(i-1)+1)%i == 0:
        print i

Takes about 15 sec. to finish

and this code (can I make the sieve more dirty than this

for n in range(2, 3000):
    for x in range(2, n):
        if n % x == 0:
            break
    else:
        print n

Takes less than 2 sec.

Yep, new kid on the block, beaten by 2000+ old algorithm.

-Eivind

[mgb]

Originally Posted by shawn

If n be any number then if (n-1)!+1 is divisible by n then n is a prime number

I know this conclusion is true but how did you reach it?