The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Determining If a Number is Prime

Date: 08/12/2004 at 21:24:52
From: Daryl
Subject: Prime Numbers

Is there a formula for finding if a number is prime?  I've written a
program that will tell you if a number is prime, but it is slow for
larger numbers because it checks all numbers between 1 and the number
to see if they are factors of the larger number.  As you can see,
checking a number in the billions would result in billions of
divisions, which takes time.

I've tried looking online, but haven't been able to find anything.

Date: 08/13/2004 at 12:21:49
From: Doctor Vogler
Subject: Re: Prime Numbers

Hi Daryl,

Thanks for writing to Dr Math.  There are several "formulas."  They
are called "primality tests."  First there are the "pseudoprimality
tests" which can quickly tell you if a number is NOT prime, but they
can not guarantee that a number IS prime.  The Fermat test is the
best-known of these.  The true primality tests are more complicated
(which is why you usually start by checking if the number is clearly
composite first, with a pseudoprimality test) but they can tell you
conclusively whether a number is prime.  In fact, a recent discovery
was a "polynomial-time deterministic primality test" which means that
it is "fast" by a particular technical definition of "fast."  Other
non-deterministic algorithms are more effective or more efficient, but
this one is interesting theory.  For precise descriptions of 
particular primality tests, search Google for "primality test."  See
also the account on MathWorld at

  Primality Test 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum 
Associated Topics:
Middle School Prime Numbers

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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

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