THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsPrime().  A prime number is an integer which can only be divided by 1 and itself, such as 7, 91, 113, etc.

At least half of all integers cannot be prime, because they're even numbers and thus divisible by 2. Then there are those that divide by 3, 5, 7, 11, etc. So the number of primes is limited.

This code will only find primes up to a maximum possible value of p. See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare IsPrime(p: int) (or whatever integer type you want).

Here's the code:


sub IsPrime(p)
' if argument p is prime returns
' TRUE (-1), otherwise returns FALSE (0)

def flag, i, root: int
if p = 2 | p = 3: 'smallest primes
    flag = -1
else
    if p % 2 = 0 | p < 2: 'even number or ineligible
        flag = 0
    else
        root = sqrt(p): 'limit of search
        i = 3
        flag = -1       
        do
            if p % i = 0: 'not prime
                flag = 0
            else
                i = i + 2
            endif
        until flag = 0 | i > root
    endif
endif
return flag   

Let's look at the variables before we begin on the code detail.

p is the variable which has been submitted by the calling routine. It's asking the question "Is p a prime number?" and expects one of two replies: TRUE (-1) or FALSE (0). IsPrimes()'s job therefore is to determine p's primality and respond accordingly.

Variable flag is used to indicate p's primality. It's set to TRUE (-1) to begin with, and will stay that way unless p is found not to be prime, at which point it will be reset to FALSE (0). The code picks the change up and aborts further investigation, making the function work more efficiently.

Variable i is used to iterate over the checks that must be made on p.

To make it simpler to follow detailed code description, I've number the lines as shown below.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

if p = 2 | p = 3: 'smallest primes
    flag = -1
else
    if p % 2 = 0 | p < 2: 'even number or ineligible
        flag = 0
    else
        root = sqrt(p): 'limit of search
        i = 3
        flag = -1       
        do: 'commence general divisibility checks
            if p % i = 0: 'not prime
                flag = 0
            else
                i = i + 2
            endif
        until flag = 0 | i > root
    endif
endif
return flag 

Now for a line-by-line exegesis of the code.

1

if p = 2 | p = 3.  This means "if p =2 or p = 3." In prime numbers, p = 2 is a special case. It's a prime number because it can only be divided by itself and 1. But it's also an even number, and normally primes can't be divided by even numbers! Later in the code we'll be checking for even numbers, and p = 2 would be mistakenly flagged up as composite (non-prime). So we have to recognise it here and take special action.

What about the case where p = 3? This is the value at which checking of primes usually begins, since division by 2 comes under even numbers and is taken care of separately. If we checked 3 for division by 3 it would also be flagged mistakenly as composite, so, once again, it's dealt with here and special action taken.

2

flag = -1. We reached this line because p equalled either 2 or 3. These are special cases, and the special action taken is to recognise them as primes and abort all other checks. is set to TRUE (-1). Due to the construction of the IF-ENDIF clauses, the code, having reached this line, jumps to the end of the function where it obeys the command to return the flag to the calling routine.

3

else. This says in effect "It turns out that p isn't equal to either 2 or 3, so we need to go on and make other checks for primality." The code then continues to execute the next lines instead of jumping straight to the end.

4

if p % 2 = 0 | p < 2. This line is effectively asking "Is p an even number or less than 2?", the two other special cases which will require special action.

Firstly, it checks that p isn't an even number with the expression
p % 2 = 0. Even numbers (except 2 itself, and we've already taken care of that special case) cannot be prime, since they can be divided by 2.

Secondly, the main routine may have submitted 1 for testing, a zero, or even a negative number, none of which can be prime, and this is caught by the expression
p < 2.

5

flag = 0We reached this line because p is an even number or it's less than 2. These are special cases, and the special action taken is to recognise them as non-primes and abort all other checks. flag is set to FALSE (0). Due to the construction of the IF-ELSE-IF-ENDIF clauses, the code, having reached this line, jumps to the end of the function where it obeys the command to return the flag to the calling routine.

6

else.   All the special case checks having failed, it's time to move onto general checks for palindromicity.

7

root = sqrt(p).  At this point in the code, we've reached the situation of having already weeded out all special cases (p equal to 2 or 3, p a regular even number, or p equal to 1 or less) so it's time to start the other checks.

These "other checks" consist of seeing if p is exactly divisible by some other number. Of vital concern for efficiency is the range of numbers to check.  If it's too small, a composite might accidentally be taken for a prime. If it's too large, unnecessary checks will be made, wasting program time.

We know the minimum number to start these divisibility checks is 3, as explained above. What about the maximum?

Look at what happens when  checking 100 for divisibiity.  Early on, we can try dividing by 4. The result is 25. Clearly, there will be no point later on in trying to divide by 25, since we know the result will be 4.

Next, try dividing by 5. The result is 20. So there will be no point in trying later to divide by 20, since we know the result will be 5.

If you think about this, you'll see that the only numbers worth checking for divisibility are those less than the square root of 100 (10). Everything greater is duplication. This is a general principle, so we need only to find the square root of p and make that our upper limit for divisibility tests.

8

i = 3.  Sets the lower limit of the search, as explained above.

9

flag = -1.  The code is going to assume p is prime unless and until divisibility checks prove otherwise, so flag is set to TRUE (-1).

10

do.  Opens the DO loop containing the divisibility checks.

11

if p % i = 0. This expression effectively says "If p divided by i leaves no remainder it must be composite." The value of p has been carefully limited between 3 and the square root of p, with even numbers excluded. If p were prime, there would be no remainder.

12

flag = 0.  If the code reaches this line, p was found in line 11 not to be prime, so flag is set to FALSE (0).

13

else.  If the code reaches this line, p's primality has not yet been disproved, so further divisibility checks will have to be made.

14

i = i + 2. Variable i is incremented ready for the next check. The incrementation is by 2, to keep i as an odd number. This improves efficiency, since a single even-number check was made in line 4, rendering all others unnecessary.

15

endif.  Housekeeping - closes IF-ENDIF clause covering divisibility.

16

until flag = 0 | i > root.   The code has reached the end of the  divisibility DO loop. It's decision time: re-execute the loop or go on to the next bit of code. There are two conditions for exit:

One, if the flag has been set to zero. This indicates that p isn't prime, and there's no point making further divisibility checks.

Two, if the last increment of i took its value above the upper check limit as store in variable root. This means that further checks are unnecessary.

17

endif. Housekeeping - closes the nested IF-ENDIF clause opened in line 4.

18

endif. Housekeeping - closes the nested IF-ENDIF clause opened in line 1.

19

return flag.  The function has finished.  Variable flag holds the value TRUE (-1) or FALSE (0), and this is returned to the calling routine.

This function is often used when the calling routine has already ensured only odd numbers greater than 3 are passed as parameter. In this situation, efficiency can be improved by deleting the special cases tests, leaving the slimmed-down code looking like this:


sub IsPrime(p)
' If argument p is prime returns
' TRUE (-1), otherwise returns FALSE (0).
' Assumes p is an odd number and
' greater in value than 3.
def flag, i, root: int
root = sqrt(p): 'limit of search
i = 3
flag = -1
d
o
    if p % i = 0: 'not prime
        flag = 0
    else
        i = i + 2
    endif
until flag = 0 | i > root
return flag 

For the really big primes, with hundreds or even thousands of digits, these conventional approaches won't work.  But they're so hard to factorise that they're used as security devices anyway, so I'll leave that for another day . . .

MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 5th, 2010.