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
is prime. In a few sentences, describe an efficient procedure she could use to answer this question.
Amazingly, it turns out that
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
are factors of
- To make this list of prime numbers, the sieve of Eratosthenes can be employed. Notice that
, 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
and
and then eliminate the nontrivial multiples of the prime numbers
.
- If none of the resulting prime numbers are factors of
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?.”
Mean Green Math 
Pretty long odds of ol’ Tommy Tutone blundering into such a significant prime number no? This was no boating accident…
I know your question was asked tongue-in-cheek, but I was curious. According to Mathematica, there are 515,646 prime numbers between 2,000,000 and 9,999,999 (since a 7-digit US phone number can’t start with either a 0 or 1). So the odds of picking a prime number at random from this list would be about 6.4%, or odds of about 14.5:1.
The odds are considerably better if we deliberately choose a phone number that doesn’t end in 0, 2, 4, 5, 6, or 8 (since clearly such numbers can’t be prime). If we deliberately avoid such numbers and don’t consider other divisibility tests — like the divisibility test for 3 — then the chances become 515,646 in 3,200,000, or about 1 chance in 6.