Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives

Primality Testing

Date: 12/02/2004 at 09:09:53
From: S. Kanagaraj
Subject: Primality Testing

How can I determine if a large number given to me is prime?  Is there
a process or test I can use?  I'm writing a C program and have tried
dividing the given number by 2 or 3 and by the numbers other than 1
and itself.  But it takes so many steps in writing my program.  Is
there a faster test?

Date: 12/02/2004 at 10:37:02
From: Doctor Vogler
Subject: Re: Primality Testing

Hi S,

Thanks for writing to Dr. Math.  The next thing you have to decide is
how much math you want to learn.  Testing for primality is not an easy
thing to do, and there are numerous methods, some of which are better
for different sizes of numbers, and some of which give better results
or have better features.  For example, on our prime number page,

  Prime numbers

there is a link to one of the simplest primality tests at

  Primality Test

This will tell you to try dividing by every number up to

  sqrt(222221) = 471.4

and you will eventually find that 222221 is divisible by 359.

A faster test, slightly more complicated but the least complicated of
the advanced tests, is the Fermat Pseudoprimality Test.  It is called
a "pseudoprimality test" because it can only tell you if a number is
NOT prime, and if it doesn't tell you that it's not prime, then it
might still be either prime or composite.  That uses modular 

  Mod, Modulus, Modular Arithmetic

and is based on the fact that


whenever p is prime and does not divide a (this is sometimes called
Fermat's Little Theorem).  So you pick a=2 or a=3 or something similar
(and perhaps try several values) and test if

  a^(n-1) = 1 (mod n).

If it doesn't, then n cannot be prime.  If it does, then... well... n
is *probably* prime.

There are many other more complicated tests, but they get harder and
harder to understand, and harder and harder to use.  But when you have
a really, *really* big number that you want to test, you generally
need a really advanced primality test.  See also

  Determining If a Number is Prime

  Exploring Fermat's Little Theorem

  Large Prime Numbers

  Primality Testing

  Prime Number Tests

  Testing primality of 32-bit numbers

  Testing Prime Numbers

offer further suggestions.

- Doctor Vogler, The Math Forum
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:


parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]


Ask Dr. MathTM