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  2^{30}  1073741824 
uint  2^{31}  2147483648 
int64  2^{61}  2305843009213693952 
uint64  2^{62}  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 linebyline 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 (nonprime). 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 IFENDIF 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 = 0. We 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 nonprimes and abort all other checks. flag is set to FALSE (0). Due to the construction of the IFELSEIFENDIF 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 evennumber check was made in line 4, rendering all others unnecessary. 
15 
endif. Housekeeping  closes IFENDIF clause covering divisibility. 
16 
until
flag = 0  i > root.
The code has reached the end of the divisibility DO loop. It's
decision time: reexecute 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 IFENDIF clause opened in line 4. 
18 
endif. Housekeeping  closes the nested IFENDIF 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 slimmeddown 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 do 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 Email me!
Last Updated: February 5th, 2010.