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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.