Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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
well as more about mathematics.  I hope this helps.

-Doctor Mike,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search