Who here thinks that humans will never uncover the formula for prime numbers?

dont you know?
Prime is a value not equal to product of Primes other than 1.

what I meant was a formula to see if ANY number was prime, without dividing it by every number half-way before it.

There is formula in Quantum Mechanics...

sure there is

What you want is a function f(n) such that f(n) = 1 if n is prime and zero otherwise. The prescription to try to divide n by all integers up to n^1/2 will do but you want a function that can be calculated faster. There are algorithms that allow you to calculate f(n) in Log(n) steps.

The idea is to use Fermat's theorem. For a fixed integer n, define X Mod n as the remainder you get when you divide X by n. So, e.g. 21 Mod 10 = 1 and 27 Mod 11 = 5. Calculations Mod n satisfy these properties which allow to quickly calculate results for large numbers:

X^r Mod n = (X Mod n )^r

A B Mod n = (A Mod n) (B Mod n)


So, e.g. to calculate 365 Mod 7 start from
10 Mod = 3 . Thus 100 Mod 7 = 3^2 Mod 7 = 2. And 365 Mod 7 = (3*2 + (-1)*3 + 5) Mod 7 = 1.
9 October 2006 will thus be a thursday!

Fermat's theorem gives a necessary condition for n if n is a prime. Consider the sequence of numbers 1, 2, 3, ...,n-1. Multiply these by some integer x smaller than n and take Mod n. Then you obtain the sequence:

x, 2x Mod n,...(n-1) x Mod n.

If n is a prime then there is no way any two different entries in the second sequence can be equal. If the r*-th and the s-th entry are equal then that would mean that (r - s)x is a multiple of n. Because r and s are both smaller than n and x is smaller than n, this is imposible because n is prime. You can't multiply smaller integers than a prime to obtain a multiple of that prime.

Because no two entries of the sequence:

x, 2x Mod n,...(n-1) x Mod n.

are the same and because there are in total n-1 entries all smaller or equal than n, this sequence is just a the original sequence 1, 2, 3, ...n-1, in a different order.

This means that if you multiply all the entries of the sequence it should have the same result as multiplying all the entries of the first sequence. But if you take out a factor x in this multiplication, the multiplication is x^(n-1) times the product of the entries in the original sequence Mod n. Therefore:

x^(n-1) = 1 Mod n if n is prime.

So, if you have some large number n and you calculate 2^(n-1) Mod n and this turns out to be different from 1 then you know that n can't be prime. The reverse is not true, because it can happen that 2^(n-1) Mod n is 1 ''by accident'' even if n is not prime. However this is unlikely if n is very large. But it is possible to give a rigorous proof for primality of any number using a bit more work. E.g. it can be shown that if
2^(n-1) = 1 mod n and if n = h q +1 for q a prime and h smaller than q^2, then n must be prime.

Example: Is 10403 prime?

To calculate 2^10402 Mod 10403 write 10402 = 2*5201 and 5201 = 1 + 5200. We can write 5200 as 400*13.

Start with 2^(13)= 8192.
Square both sides:

2^(2*13)= 8192^2 = 9514 Mod n

Square again (ommiting the mod n sign):

2^(4*13)= 9514^2 = 10096

We need to raise this to the 100-th power. 100 = 2*2*5*5. To raise to the fifth power you just square it twice and multiply it with the original number:

2^(2*4*13)= 10096^2 = 622

2^(2*2*4*13)= 622^2 = 1973

2^(5*4*13)= 1973 * 10096 = 8066

2^(2*5*4*13)= 8066^2 = 10397

2^(2*2*5*4*13)= 10397^2 = 36

2^(5*5*4*13)= 36*8066=9495

2^(2*5*5*4*13)= 9495^2 = 2627

2^(5200)=2^(400*13)= 2^(2*2*5*5*4*13)= 2627^2 = 3940

2^(5201) = 2*3940 = 7880

Finally, 2^10402 = 7880^2 = 9296

So, we needed just 13 simple operations to find out that 10403 is not prime.

For n=1,2,3... prime numbers are generated by

n^2 - n + 41

Was that so hard?

But not nearly so impresive as a page full of doing it the hard way.

Let's see..

n=103 n^2-n+41=10547 = 53*199
n=105 n^2-n+41=10961 = 97*113
n=110 n^2-n+41=12031 = 53*227
...

This is what I thought

e s

hahah
really there is no clasical formula except the one I gave you at the begining.
All other apporaches are restatement of I said.
In Qunatum World things get solved non-sequentially. Multiple Dimesions get involved in its calculation. Making the solution fast to very fast depending upon the ability to make the ideal mesurement after time T out of ideal experiment P.The Time T is very small as compared classical calculation time t.

So you've fell for this crap, hah.

e s

So you've fell for this crap, hah.
REP: No Boss.This is a fact.Things get solved along multiple Dimensions...It a hard reality...
Tomorrow whoever knows how to construct or use such a Device will actually be called a Superior Species.

Are you watching too much of Deeeep Space?

:rolleyes:

The power of such computers are unimaginarily huge.The realizable power of its solvin speed depends on the higher level dimensional understanding of m-theory.Thus more exploration is needed in the m-theory to fullfil and realize the dream of most the effective Qunatum State for doing the calculation.

Your sense of humor borders insanity - and how we do decide?

E s