Skip to content
February 5, 2015

Let’s get primed on the primes

Jeopardy! doesn’t give a lot of love to math, but I was happy to see prime numbers dominate my list of 10 potential topics.

Any whole number larger than 1 falls into one of two categories: prime or composite. It’s the first grouping that we’ll focus on here.

Until the 1970s, prime numbers had little use outside of the world of math. More on that in a bit; let’s start with the basics.


Wolfram MathWorld will tell you the formal definition of a prime number:

a positive integer p>1 that has no positive integer divisors other than 1 and p itself

Oh please make my head stop spinning.

2 train animation 3 train animation 5 train animation 7 train animation

Here’s another way to think about primes.

If you can arrange a certain number of things in a rectangle, then that number is not prime.

Let’s say you buy a dozen donuts. Most places will give them to you in a box 4 donuts wide and 3 donuts deep.

Since you can arrange these 12 donuts in a rectangle, the number 12 is not a prime number.

Dozen Krispy Kreme donuts

Please line up in an orderly fashion.

13, on the other hand, is a prime number. Have you ever wondered why you can get a baker’s dozen of bagels, but not of donuts?

Donuts are messy, so they need to be placed side-by-side. There’s no good shape that will take care of this, unless you’ve got a reeeeeeally long box.

There’s no frosting on bagels, so you can just toss them into a bag.

Bakers dozen donuts

Raise your hand if you can sympathize with this situation.

We now have a good idea of what prime numbers are – but how, exactly, do we identify them?

Small primes

The smallest prime number is 2. Can’t make much of a rectangle out of two points.

It’s also the only even prime number, because any other even number can be put into a rectangular box 2 donuts wide.

Then there’s 3. But not 4! Although 5 and 7 work, too.

I could keep naming random-sounding numbers – or I could introduce you to the Sieve of Eratosthenes.

Sieve of Eratosthenes

Eratosthenes (c. 276–195 B.C.) was an incredible dude. Here’s a short selection of his accomplishments beyond prime numbers:

  • Eratosthenes bustBecame head of the Library at Alexandria by the age of 40
  • Calculated the Earth’s circumference (~40,000 km) to within 15%, and axial tilt (23 ½°) nearly exactly
  • Created geography, including the concept of longitudinal parallels
  • Devised the leap year
  • Wrote the definitive history of the Olympic Games

His followers called him pentathlos, as if he were a well-rounded athlete; his detractors called him beta, as he was never the best (alpha) in any field.

He’s come up just six times on Jeopardy!, and always as part of a clue. Which is a shame, because his name is fun to say aloud.

Checking one number

Is 227 prime? Maybe you need to know this for some reason.

Here’s a trick: just check the primes up to the square root of 227. Why up to the square root?

Well, if a number larger than the square root is a factor, then it must be multiplied by something smaller than the square root.

For example, 17 is a factor of 51 (the square root of which is slightly larger than 7). But 17 * 3 = 51, so you would have caught the 3 on the way up.

227 is slightly larger than 225 (15 * 15), so we’d need to check only 2, 3, 5, 7, 11, and 13. Turns out it is, indeed, prime.

Mersenne primes

Mersenne

Two primes! Eh! Eh! Ehhh!

A Mersenne prime is a prime number of the form 2p – 1, where p is itself a prime number. That means it’s 1 less than a power of 2 (keep multiplying 2 by itself: 2, 4, 8, 16, 32… then subtract 1).

They’re named for 17th century French monk Marin Mersenne (right), just one of many who worked on these numbers, but who was lucky enough to get the namesake.

Many of his conjectures turned out to be false, but smart marketing sometimes beats good product.

One of my favorite numbers, 127, is a Mersenne prime: 27 – 1.

Big primes

The highest-known prime number is 257,885,161 – 1, which has 17,425,170 digits. Printing it out using standard font and paper size would require nearly 5,000 pages, single-sided.

Proving it was prime took 39 days of work by a single computer.

It was found as part of Great Internet Mersenne Prime Search. GIMPS was the first distributed computing project, in which people around the world offer their computers’ processing abilities during down time. (Over 100,000 users contributed today alone.)

Whoever finds the first prime number of 100,000,000 digits or more will receive a $150,000 prize from the Electronic Frontier Foundation.

With the amount of work you’d have to put into that, you might as well just try to go on Jeopardy! and win 7-8 games or so.

Primes enter the real world

Big primes are key to a ubiquitous encryption technology called RSA, first described in 1977(!).

Named for its founders – Rivest, Shamir, Adleman – the system multiplies together two very large prime numbers, because that product is very difficult to factor.

As a simplified example: let’s say my prime numbers are 11 and 13. I would publish the number 143 (equal to 11 * 13) and a second number as my public key. (This would be easy to crack, of course; the primes actually used are much, much, larger.)

Anyone can see this public key and use it to send me a message. Decoding the sent message, however, requires knowledge of those two original prime numbers.

It’s a bit like a mailbox: anyone can drop mail in the slot, but only the person with the key – the intended recipient – can open it.

Cracking the prime code?

In 1858, the German mathematician Bernhard Riemann suggested a way to find the distribution of prime numbers. He failed to provide a proof, however, and countless mathematicians since have failed to do so, as well.

Schoenfeld 1976

Get out of here, nerd! (Schoenfeld, 1976)

The Riemann hypothesis is one of the great unsolved mysteries in all of mathematics; if it’s proven, it would likely destroy prime-based encryption technology, since prime numbers would be much easier to identify.

In 2000, the Clay Mathematics Institute named it one of seven Millennium Prize Problems, meaning whoever cracks it will receive $1,000,000.

Now THAT might be worth your time. Just don’t turn it down like the first (and so far only) winner did.

One final note

With all of this talk about computers and such, a throwback to the Greeks: Euclid proved that there is an infinite number of primes. Happy hunting!

3 Comments
  1. Chuck C permalink

    Interesting that they do the Prime check on essentially a graphics card — the same one that I have in my PC.

    • That’s a good point – a lot of processors are tested by their performance on a prime-number search before they’re ever put into a computer.

  2. Pat Russell permalink

    Your animation does not seem to be working for the 10s column. They should all be wiped out when you sieve on 5.

What do you think?