Q: Is there a formula for finding primes? Do primes follow a pattern?

Physicist: Primes are, for many purposes, basically random.  It’s not easy to “find the next prime” or determine if a given number is prime, but there are tricks.  Which trick depends on the size of the number.  Some of the more obvious ones are things like “no even numbers (other than 2)” and “the last digit can’t be 5”; but those just eliminate possibilities instead of confirming them.  Confirming that a number is prime is a lot more difficult.

Small (~10): The Sieve of Eratosthenes finds primes and also does a decent job demonstrating the “pattern” that they form.

Starting with 2, remove every multiple. The first blank is a new prime. Remove every multiple of that new prime. Repeat forever or until bored.

The integers come in 4 flavors: composites, primes, units (1 and -1), and zero.  2 is the first prime and every multiple of it is composite (because they have 2 as a factor).  If you mark every multiple of 2, you’ll be marking only composite numbers.  The first unmarked number is 3 (another prime), and every multiple of 3 is composite.  Continue forever.  This makes a “map” of all of the primes up to a given number (in the picture above it’s 120).  Every composite number has at least one factor less than or equal to its square root, so if the largest number on your map is N, then you only need to check up to √N.  After that, all of the remaining blanks are primes.

This algorithm is great for people (human beings as opposed to computers) because it rapidly finds lots of primes.  However, like most by-hand algorithms it’s slow (by computer standards).  You wouldn’t want to use it to check all the numbers up to, say, 450787.

Eratosthenes, in a completely unrelated project, accurately calculated the circumference of the Earth around 2200 years ago using nothing more than the Sun, a little trigonometry, and some dude willing to walk the ~900km between Alexandria and Syene.  This marks one of the earliest recorded instances of grad student abuse.

Medium (~10¹⁰): Fermat’s Little Theorem or AKS.

Fermat’s little theorem (as opposed to Fermat’s theorem) works like this: if N is prime and A is any number such that 1<A< N, and if , then N is definitely composite and if then N is very likely to be prime.  “Mod N” means every time you have a value bigger than N, you subtract multiples of N until your number is less than N.  Equivalently, it’s the remainder after division by N.  This test has no false negatives, but it does sometimes have false positives.  These are the “Carmichael numbers” and they’re more and more rare the larger the numbers being considered.  However, because of their existence we can’t use FLT with impunity.  For most purposes (such as generating encryption keys) FLT is more than good enough.

For a very long time (millennia) there was no way to verify with certainty that a number is prime in an efficient way.  But in 2002 Primes is in P was published, which introduced AKS (Agrawal–Kayal–Saxena primality test) that can determine whether or not a number is prime with complete certainty.  The time it takes for both FTL and AKS to work is determined by the log of N (which means they’re fast enough to be useful).

Stupid Big (~10¹⁰¹⁰): Even if you have a fantastically fast technique for determining primality, you can render it useless by giving it a large enough number.  The largest prime found to date (May 2014) is N = 2^57,885,161 − 1.  At 17.4 million digits, this number is around ten times longer than the Lord of the Rings, and about twice as interesting as the Silmarillion.

Number of digits in the largest known prime vs. the year it was verified.

To check that a number this big is prime you need to pick the number carefully.  The reason that 2^57,885,161 − 1 can be written so succinctly (just a power of two minus one) is that it’s one of the Mersenne primes, which have a couple nice properties that make them easy to check.

A Mersenne number is of the form M_n = 2ⁿ -1.  Turns out that if n isn’t prime, then neither is M_n.  Just like FLT there are false positives; for example M₁₁ = 2¹¹ -1 = 23×89, which is clearly composite even though 11 is prime.  Fortunately, there’s yet another cute trick.  Create the sequence of numbers, S_k, defined recursively as S_k = (S_k-1)² – 2 with S₀ = 4.  If , then M_p is prime.  This is really, really not obvious, so be cool.

With enough computer power this is a thing that can be done, but it typically requires more computing power than can reasonably be found in one place.

Update (Jan, 2016): The largest known prime is now 2^74,207,281 – 1.

Update (Jan, 2019): The largest known prime is now 2^82,589,933 – 1.

Answer Gravy: Fermat’s little theorem is pretty easy to use, but it helps to see an example.  There’s a lot more of this sort of thing (including a derivation) over here.

Example: N=7 and A=2.

[2^7-1]₇ = [2⁶]₇ = [64]₇ = [64-9×7]₇ = [64-63]₇ = 1

So, 7 is mostly likely prime.

Example: N=9 and A=5.

[5^8-1]₉ = [5⁷]₉ = [25x25x25x5]₉ = [7x7x7x5]₉ = [49×35]₉ = [4×8]₉ = [32]₉ = 5

Astute readers will note that 5 is different from 1, so 9 is definitely not be prime.

For bigger numbers a wise nerd will typically exponentiate by squaring.

Example: N=457 and A=2.  First, a bunch of squares:

As it happens, 457-1 = 456 = 256 + 128 + 64+8.

So 457 is very likely to be prime (it is).  This can be verified with either some fancy algorithm or (more reasonably) by checking that it’s not divisible by any number up to √457.