http://www.factmonster.com/math/numbers/prime.html A prime number can be divided, without a remainder, only by itself and by 1. For example, 17 can be divided only by 17 and by 1. Some facts: The only even prime number is 2. All other even numbers can be divided by 2. If the sum of a number's digits is a multiple of 3, that number can be divided by 3. No prime number greater than 5 ends in a 5. Any number greater than 5 that ends in a 5 can be divided by 5. Zero and 1 are not considered prime numbers. Except for 0 and 1, a number is either a prime number or a composite number. A composite number is defined as any number, greater than 1, that is not prime. To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number

Tip: (n*6)+/-1

This is the fastest method if you have a bound: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

Bertrand's postulate (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n <p> 1 there is always at least one prime p such that n < p < 2n. So if I am given a number, say n, than I can check in the range (n, 2*n) [open interval excluding n and 2*n] int GetNextPrime(int n) { bool isPrime = false; int i = n; for (; i < 2 * n; ++i) { // go with your regular prime checking routine // as soon as you find a prime, break this for loop } }</p>