THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  GetNextPrime(). When a prime number is passed to function GetNextPrime(), it simply finds the prime number whose value is closest to (but greater than) its argument and returns it to the calling routine.

The parameter passed should be a prime number.  The function will still work correctly if the parameter is non-prime but an odd number.  It will always fail for even numbers.

Note that this function in turn calls another function IsPrime().  If you want to view the IsPrime() function, click here now.

It's up to you what kind of integer you pass to the function, as long as the function declaration has already taken this data-typing into account. See the table below for the parameter 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 GetNextPrime(g: int) (or whatever integer type you want).

Here's the code:


sub GetNextPrime(g)
' Finds the next integer greater
' than argument g which is prime
' and returns it.
' Assumes g is an odd number.

def flag: int
flag = 0
do
    g = g + 2
    if g % 5 = 0
        g = g + 2
    endif
    if IsPrime(g)
        flag = -1
    endif
until flag
return g

Overview:   argument g is already an odd number.  Since primes are always odd numbers (at least, those greater than 2), the function will only ever look for numbers which are multiples of 2 greater than g, ensuring that they must also be odd numbers.

Within a DO-LOOP, g is incremented by two every pass. If this latest increment caused g's last digit to be a 5, we know it's not prime (primes only ever end in 1, 3, 7, or 9) and g is immediatedly incremented again. g can now be submitted as parameter to function IsPrime().  If g is a prime, IsPrime() returns TRUE (-1), otherwise FALSE (0).

If TRUE (-1) is returned from IsPrime(), GetNextPrime's variable flag is set to TRUE as well. If FALSE is returned from IsPrime, GetNextPrime's variable g is incremented by 2.

At the end of the DO-LOOP, flag is examined.  If it's still at its initialised value of FALSE, the loop is executed again in another attempt to find a prime.  If it's set to TRUE, the DO-LOOP is exited and g's new value returned to the calling routine.

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


1
2
3
4
5
6
7
8
9
10
11
12

def flag: int
flag = 0
do
    g = g + 2
    if g % 5 = 0
        g = g + 2
    endif

    if IsPrime(g)
        flag = -1
    endif
until flag
return g

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

1

def flag: int.  Local variable flag is defined.  It will be used by the code later to signal the task is complete.

2

flag = 0.  Initialises local variable flag to zero.  You will see when we get to line 11 that, while this value is maintained, the code will keep re-executing its DO-LOOP.


3

do.  Opens main DO-LOOP.

4

g = g + 2.  Local variable g is the function's argument, passed into it by the calling routine.  It will be a prime number, and the GetNextPrime()'s task is to find the next highest prime to g.

Obviously, we have to increment g to find a higher prime than g.  Since g itself was originally a prime, and thus an odd number, incrementing by 1 will make it an even number. But primes are always odd numbers (apart from 2), so obviously there's no point in incrementing just by 1. The smallest increment must be 2, to keep g odd and thus give it a chance of being prime again.

5

if g % 5 = 0g could possibly finish in 5 by now. We need to know this, since primes can only end in 1, 3, 7, or 9. This line uses integer arithmetic to find out. It can be paraphrased as "if the remainder after dividing g by 5 is zero ..." If it is zero, it must end in 5 (or 0).

6

g = g + 2.  The code only reaches this line if g ends in a 5. It can't be prime, since no integer (except 5 itself) ending in 5 is prime. In such a case, it can be immediately incremented again so that it has a chance of being prime.

7

endif.  Housekeeping - closes IF-ENDIF clause.

8

if IsPrime(g).  We just incremented g by 2. Now is the time to check if the new value is prime.  g is passed to the function IsPrime() for that purpose.

9

flag = -1.  If the code reaches this line, IsPrime() found g was prime and returned TRUE.  So the code sets flag to TRUE (-1) to mark this event.  It will be used to halt the search for further primes, since one has been found.  The code will jump from here to line 9, since no alternative action is necessary.

10

endif.  Housekeeping - closes IF-ENDIF clause.

11

until flag.  This line is the decision-maker.  It can be paraphrased as "execute the DO loop again unless variable flag is set to TRUE (-1)."

12

return g.   Once the function reaches this line, its task is all but complete.  The DO-LOOP has been exited, which means that a new prime has been found, which will be stored in variable g at this time.  All that remains is to return that value to the calling routine, and that's what this line does.


MAIN MENU
HOW DOES IT WORK?

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