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

### Primality Test

```
Date: 11/26/2001 at 04:47:41
From: Maria
Subject: Prime numbers

Hi Dr Math,

I want to write a program using Pascal, and I am required to enter any
number in my program, which should then say if it is a prime number or
not. I want to know if there is any formula for prime numbers.
```

```
Date: 11/26/2001 at 08:33:19
From: Doctor Paul
Subject: Re: Prime numbers

This is a problem that mathematicians have been working on solving for
thousands of years. There are some special types of primality tests
that require some pretty advanced mathematics. But I think the most
basic test is as follows:

First notice that all of the divisors of a number come in pairs:

For example, if I pick 48 its divisors are:

1,48
2,24
3,16
4,12
6,8

The key is to notice that all of the first numbers occur before
sqrt(48).

If the number had been 49, I would write the divisors as:

1,49
7,7

Here one of the divisors is sqrt(49).

So what we notice is that if a number n has a divisor greater than one
(which would make the number a non-prime), it must be less than or
equal to sqrt(n).

So you just need to run a for loop that tests to see if any number
from 3 (clearly you don't need to test 2 - if the number is even and
greater than two, it can't be prime) up to sqrt(n) divides evenly into
the given number. If you find one, then the number isn't prime. If you
don't find one, the number is prime.

So how do you test divisibility? Why don't you try looking at the
remainder when you divide your number n by 3, 4, 5, etc...

If you ever get a remainder of zero, then you have found a factor and
the number isn't prime.

I don't know about pascal, but c++ has a modulus operator (the %
symbol) that returns the remainder when you divide a by b. For
example:

22%7 would return 1 because 22 is one more than a multiple of 7.

If pascal has a similar command, this is the way to go. Otherwise,
you'd have to be a bit more sly. If you are testing the number 77
for primality (it isn't prime since 77 = 7*11) and, say, you are up
to 77/5

Have the computer write this as a decimal:

77/5 = 15.4

What you want to have the computer do is check to see if the number
has a non-zero part after the decimal.

So first run an until loop that subtracts one from the number until it
is less than one and bigger than or equal to zero.

In the case above, the computer would stop when the number was .4

Now test to see if this number is zero. If it is zero, then you've
found a factor and the number isn't prime. Otherwise you conclude that
this particular divisor didn't divide evenly into the number being
tested, so you increase the divisor by one and try again.

There are other - probably better - ways to test for divisibility as
well. But this should at least give you a start.

I hope this helps. Please write back if you'd like to talk about this
some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/08/2006 at 08:34:29
From: Josh
Subject: More convienent Prime Number Testing - no modulus

My question isn't a question, so much as a helpful tip to you, Dr.
Math.  Your database of answers has helped me through the years with
many of my problems, so I would like to contribute back if I can.

I'm working on a prime number tester, and I was taking a look
through your articles, when I noticed that one of your answers to a
patron involved what to do if you had no modulus function.  You told
him to create a loop to subtract 1 from the division of the problem
until it was less than one, then test if it was equal to 0.  Instead,
most of the programming languages will include some sort of flooring
or rounding down function, like C++ in the math.h library.  Therefore,
you could make an IF statement to test "(X/Y)=FLOOR(X/Y)".

For example, if you wanted to test if 10 was evenly divisble by
three.  11/3 = 3.667, and FLOOR(10/3) = 3.  Since the two are not
equal, 3 is not a divisor of 10, and you can move on to the next
number.  However, testing 12 and 3, you get 12/3 = 4, and FLOOR
(12/3) = 4.  Since the two are equal, 4 is a divisor of 12, and you
can stop.

I hope this helps you, and maybe some other person out there in the
world.  Thanks for all your help over the years, Dr. Math.
```

```
Date: 02/08/2006 at 09:51:35
From: Doctor Peterson
Subject: Re: More convienent Prime Number Testing - no modulus

Hi, Josh.

You're right that the suggested workaround is about as inefficient
as you can get; probably Dr. Paul was offering an alternative that
could work in the most basic language imaginable, and didn't even
want to assume it had a floor function.

Actually, all you need a language to support is integer division
(or, equivalently, the ability to convert a "real" or "floating
point" number to an integer, which will do essentially what "floor"
does).  For your purposes, merely testing divisibility, your
suggestion is good; one might write it as

if (a/b = int(a/b))
// a is divisible by b

if "int" converts a number to an integer.  In fact, you can even
write a "mod" function using this:

mod(a, b) = a - b * int(a/b)

This will be zero when a is divisible by b, and otherwise will be
the remainder.

All of this ignores some problems when either number is negative;
I've dealt with that elsewhere, but you wouldn't need it in dealing
with primes. See

What is Mod?
http://mathforum.org/library/drmath/sets/select/dm_mod.html

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/22/2006 at 13:31:31
From: Josh
Subject: Thank you (More convienent Prime Number Testing - no modulus)

Hey, I didn't even think of that!  You're right about the whole
negative numbers thing, and I understand the idea of working with the
simplest language possible.  Thanks for your comments and suggestions!

- Josh
```
Associated Topics:
High School Calculators, Computers
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