The isPrime() Algorithm

The isPrime() method should employ a loop to find whether its parameter, N, is a prime. The algorithm in this case should make use of the definition of a prime number -- that is, a number divisible only by itself and 1. It could try dividing N by K, where K is $2,3,4,5\ldots$ and so on up to N-1. If any of these numbers is a divisor of N, then N is not a prime number. If none is a divisor of N, then N is a prime number. Because the number of iterations required for this loop is not known beforehand, it will require a noncounting loop structure.

To test whether N is prime it is necessary to have an entry condition that is the conjunction of two conditions. The loop should iterate while K is less than N, and while none of the preceding values of K were divisors of N. In other words, the loop should terminate when a value K is found that evenly divides N. One way to handle this task is to use a local boolean variable as a flag  that will be raised when a value K is found that divides N:

    Initialize notDivisibleYet to true
    Initialize K to 2
    while (notDivisibleYet AND K < N)  {
        if N is divisible by K
            set notDivisibleYet to false
        increment K;
    }

This is an example of a complex loop bound . It involves the conjunction of both a count bound and a flag bound and it will terminate when either bound is reached. Thus the loop terminates when either K equals N or when N is divisible by some value of K < N.

Note that for the conjunction notDivisibleYet AND K < N to be true, both halves of it must be true. However, for it to be false, either half may be false; it is not necessary that both halves be false. In this case either notDivisibleYet will be false or $K \geq N$ will be false. This is an instance of the logic rule known as DeMorgan's Law , which can be stated as follows:

    ((P && Q) == !(P || Q))

where P and Q are simple boolean conditions.

To summarize, the above loop structure can be used in isPrime(N) to test whether N is prime. In order to decide whether N is a prime, isPrime() must check which bound actually terminated the loop, and then return the proper boolean result. If the loop terminated with K equal to N, it follows that N is prime, and isPrime() should return true. Otherwise N is not prime and it should return false.