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