Determine whether a number is prime How do I determine if a number is prime?  I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?

How do I mathematically determine if a number is prime?
If the number is n, then dividing it by every prime number less than or equal to sqrt(n) and showing that there is a remainder.
There are a number of different sieve solutions for finding prime numbers, the oldest and most famous of which is the Sieve of Eratosthenes.  These are generally easy to programme and can, for example, find all of the primes below 100,000 in a few milliseconds on a modern processor.
