How do you find Prime Numbers?

A Math Forum Project

Table of Contents:

Famous Problems Home

The Bridges of Konigsberg
· Euler's Solution
· Solution, problem 1
· Solution, problem 2
· Solution, problem 4
· Solution, problem 5

The Value of Pi
· A Chronological Table of Values
· Squaring the Circle

Prime Numbers
· Finding Prime Numbers

Famous Paradoxes
· Zeno's Paradox
· Cantor's Infinities
· Cantor's Infinities, Page 2

The Problem of Points
· Pascal's Generalization
· Summary and Problems
· Solution, Problem 1
· Solution, Problem 2

Proof of the Pythagorean Theorem

Proof that e is Irrational

Book Reviews



Good question. It's one mathematicians are still trying to answer. The simplest method was developed by Eratosthenes in the 3rd century B.C. Here's how it works: Suppose we want to find all the prime numbers between 1 and 64. We write out a table of these numbers, and proceed as follows. 2 is the first integer greater than 1, so it is obviously prime. We now cross out all multiples of two. The next number that we haven't crossed out is 3. We circle it and cross out all its multiples. The next non-crossed-out number is 5, so we circle it and cross out all its multiples. We only have to do this for all numbers less than the square root of our upper limit (in this case sqrt(64)=8) since any composite number in the table must have at least one factor less than the square root of the upper limit. What's left after this process of elimination is all the prime numbers between 1 and 64.

Unfortunately, this method is rather time-consuming when the numbers you are looking for are much larger.

More Prime Number Theory

Mathematicians have developed a great amount of theory concerning prime numbers. Here's a taste of it:

Question: how far are prime numbers from each other? Sometimes, only 2 integers apart, like 41 and 43. Although there is a lot of evidence to suggest it, no one has proved that there are an infinite number of "twin primes."

In general, however, primes get more spread out as they get larger. By how much? In 1896 Charles de la Vallee-Poussin and Jacques Hadamard proved the Prime Number Theorem, which states:

Let Pr(x) be the number of prime numbers less than x. Then the ratio of Pr(x) to (x/ln(x)) approaches 1 as x grows without bound.

What this implies is that if n is a prime number, the distance to the next prime number is, on average, approximately ln(n).

The Goldbach Conjecture
In a letter to Leonard Euler in 1742, Christian Goldbach conjectured that every positive even integer greater than 2 can be written as the sum of two primes. Though computers have verified this up to a million, no proof has been given. Since Goldbach's time, however, his idea has been broken down into the 'strong' Goldbach conjecture - his original claim - and the 'weak' Goldbach conjecture, which claims that every odd number greater than 7 can be expressed as the sum of three odd primes. Try it and see!

to Prime Numbers
to Famous Paradoxes

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help 

© 1994- The Math Forum at NCTM. All rights reserved.

August, 1998