Thursday, July 24, 2008

Formula for Primes

I stumbled on two interesting formulas for primes today. The first formulas allows to check if a certain number is prime or not, and the second formulas gives you the Nth prime. They both use factorials, so neither of them is efficient for large numbers. And since n! becomes large rather rapidly, it means that without a computer it would be a problem to use this formula even for n=20 for example.

Both of the formulas were invented by C.P Willans. The | | stands for the floor function.

If x is prime, the result will be 1 else it will be zero.

As you can see both of them are higly ineficcient - the numbers becomes laege extremely fast.