counting primes

Tuesday 2 December 2014

Even though they do not need to know it for any exam question, I think any student in IB Math HL or SL should be familiar with Euclid's famous proof of the infinitude of primes. The only formal proof method that a Math HL student is required to know is proof by mathematical induction. A far more elegant (and perhaps better understood by most students) method of proof is a proof by contradiction - and Euclid's proof that there are an infinite number of prime numbers is probably the best known example of this method. Below is a fairly clear explanation of Euclid's proof taken from a site by Peter Alfeld, a professor of mathematics at the University of Utah.

So, what's the point of this blog post? Before I answer that, let me mention two observations of mine from many years in the classroom. Firstly, most students are intrigued by prime numbers - finding them, counting them, finding the website with the largest known prime, etc. And, secondly, the programming capability of graphing calculators - especially the more recent models such as the TI-Nspire CX - is often overlooked as a tool for student exploration (not to mention learning the basics of programming). Combining these two observations, I often show students the fundamentals of how to program on their TI-Nspire and challenge them to write a short program to count the number of primes between two given numbers (inclusively). The program can be quite short especially if students are made aware of the fact that there is a built-in command on the TI-Nspire that determines whether a given number is prime or not.

Here is a program that one of my students recently wrote. Not sure you could make it much shorter. The output (shown below the program listing) is very nice. In another blog post, I'll report on how students have made further investigations on how their results from using this program compares to the prime number counting function - and its many approximations.

9592 primes less than or equal to 100 000 (only took TI-Nspire computer software about 1 second to compute this)


Tags: prime number, program, calculator, proof


Comments


To post comments you need to log in. If it is your first time you will need to subscribe.