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.
