# Is 8,675,309 prime?

This semester, to remind today’s college students of the greatness of the 1980s: I made my class answer the following question on an exam:

Jenny wants to find out if $8,675,309$ is prime. In a few sentences, describe an efficient procedure she could use to answer this question.

Amazingly, it turns out that $8,675,309$ is a prime number, though I seriously doubt that Tommy Tutone had this fact in mind when he wrote the classic 80s song. To my great disappointment, nobody noticed (or at least admitted to noticing) the cultural significance of this number on the exam.

Naturally, I didn’t expect my students to actually determine this on a timed exam, and I put the following elaboration on the exam:

Although Jenny has a calculator, answering this question would take more than 80 minutes. So don’t try to find out if it’s prime or not! Instead, describe a procedure for answering the question and provide enough details so that Jenny could follow your directions. Since Jenny will need a lot of time, your procedure should be efficient, or as quick as possible (even if it takes hours).

Your answer should include directions for making a certain large list of prime numbers. Be sure to describe the boundaries of this list and how this list can be made efficiently. Hint: We described an algorithm for making such lists of prime numbers in class. (Again, do not actually construct this list.)

I thought it was reasonable to expect them to describe a process for making this determination on a timed exam.  Cultural allusions aside, I thought this was a good way of checking that they conceptually understood certain facts about prime numbers that we had discussed in class:

• First, to check if $8,675,309$ is prime, it suffices to check if any of positive prime numbers less than or equal to $\sqrt{8,675,309} \approx 2,945.387\dots$ are factors of $8,675,309$.
• To make this list of prime numbers, the sieve of Eratosthenes can be employed. Notice that $\sqrt{2,945} \approx 54.271\dots$, and the largest prime number less than this number is 53. Therefore, to make this list of prime numbers, one could write down the numbers between $2$ and $2,945$ and then eliminate the nontrivial multiples of the prime numbers $2, 3, 5, 7, 11, \dots 53$.
• If none of the resulting prime numbers are factors of $8,675,309$, then we can conclude that $8,675,309$ is prime.

I was happy that most of my class got this answer either entirely correct or mostly correct… and I was also glad that nobody suggested the efficient one-sentence procedure “Google Is 8,675,309 prime?.”