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?
For very small numbers (less than a million), trial division is the best way: divide by 2, 3, 5, and so on until the square root of the number.  If you find a factor, the number is composite; otherwise, the number is prime.

For larger numbers there are better methods, but choosing which one depends on how much work you're willing to put into the program.  It is now known that there are no BPSW-pseudoprimes below $2^{64}$, so if you can write that test (see here for details) then you have a very quick test for primality.

If you only need to test up to $2^{32}$, you can simply check if the number is a 2-strong pseudoprime.  If so, test if it's one of 2314 exceptions (this can be done in 12 or 13 steps with a binary search); if the test fails or it's an exception, the number is composite, otherwise prime.  (You can go higher than $2^{32}$ if you're willing to build an appropriate table of exceptions.)

For larger numbers, the work is usually split into two parts: determining with high probability (say, 99.99999999%) that the number is prime, then actually proving that it is.  What type of proof depends on the form and size of the number.
Construct a list of primes up to the maximum input $n$. (Construct using prime sieves.) Then, trial division for every such prime $\le \sqrt{n}$. This should work.