Programs to Find Prime Numbers

Date: 11/27/96 at 19:34:33
From: Stephen Mcneil
Subject: Prime numbers

Dear Dr. Math,

Can a program be written in BASIC to compute the number of prime 
numbers < n?

Thank you.

Date: 11/28/96 at 00:43:17
From: Doctor Mike
Subject: Re: Prime numbers

Hi Stephen,

Your question shows how computers can be closely connected to learning 
about parts of mathematics. 
  
My answer will apply not only to BASIC but also to other important 
high level languages such as FORTRAN, PASCAL and C++. They all have
subroutines (GOSUB and RETURN in BASIC) and loops (FOR and NEXT in 
BASIC) which are the building blocks that you need. I assume that you 
have some familiarity with BASIC and these 2 important programming 
tools.
  
You should start out by writing a simpler program that just asks for 
an input number N and tells you yes/no whether it is prime. You can 
do this just by dividing every number less than N into N to see if N 
is evenly (no remainder) divisible by it. Once you find such a number, 
you will have found a divisor and you can conclude that N is composite 
(not prime). If you never find a divisor, then N is prime. This 
program will be slower than molasses in January, but it can be speeded 
up with a trick that uses an important fact about numbers.  You do not 
have to divide ALL the numbers less than N into N to check whether it 
is prime. You just have to check all the numbers less than or equal 
to the square root of N. That is because if N has a prime factor 
other than itself, then one of them must be less than or equal to the 
square root of N. (How would you prove that?  Try assuming the 
opposite, that all factors are greater than the square root of N, and 
see what happens). 
  
OK, now that you have written and de-bugged and perfected this first
program, turn it into a subroutine. You will use this subroutine to
do the dirty work of the program you are really asking about. Your
next routine will be sort of a manager, not really doing all of the
work of finding how many primes are less than or equal to a given 
number, but having the subroutine do the work and keeping track of the 
results. Here's how it will work.
  
The new program will ask for an input number K and find out how many
primes there are less than or equal to K. Start by setting a counting 
variable NUM = 0. Set up a loop with N going from 1 to K. Each time 
through the loop, the subroutine will be executed to find out if that 
N is prime. If it is, execute the statement NUM = NUM+1, else do 
nothing.  By the time you get all the way through the loop the
variable NUM will have been increased by 1 ("bumped" or "incremented")
each time a prime was encountered, so its final value will be the
number of primes less than or equal to N. Then print your NUM as the 
answer. 

This program will not be terribly efficient or fast, but with the 
speed of PC's and Mac's these days, it will do nicely for checking 
numbers well up into the thousands. 
  
This is a nice type of programming problem for after you learn a bit
about programming.  It will help you learn more about programming as 
well as more about mathematics.  I hope this helps.  

-Doctor Mike,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/