Physics and Astronomy
Home Our Teaching Resources C programming Example: prime number test
Contents

# Example: a prime number test

Here we show a complete program, which uses the logical && in its while condition. The task is to determine whethr a number is prime, and if not to print its smallest factor. The algorithm is simple: we try all the potential factors up to and including its square root and look for one that divides it exactly.

A few points are worth noting:

• The test to see if an integer is an exact multiple of another is: int1 % int2 != 0
• As mentioned in the notes we are allowed to use &&, || etc. inside the controlling expression of a while() or for() loop.
• The rules for converting positive floating-point numbers to integers (discard the fraction), mean that the code:
int intvar;
intvar = sqrt(5);

sets intvar to be the largest integer less than or equal to the square root of 5, ie 2.

//
// Print the lowest factor of an integer or say that it is prime.
// Written to illustrate the while() loop
// The basic algoritm is to try every possible factor up to the square
// root of the number being looked at (the target)
//
#include <stdio.h>
#include <math.h>

int main() {
int target, factor, maxfactor;

target = 55;

maxfactor = sqrt(target); // Largest factor we need to try

factor = 2;
while ( target % factor != 0 && factor <= maxfactor )
++factor; // factor = factor + 1

if ( factor > maxfactor )
printf("%d is prime\n", target);
else
printf("\t%d is not prime, its lowest factor is %d\n",
target, factor);

return 0;
}
Step through this code

### Optional: some details

#### Empty loops

We could have chosen to write the main loop using the for() statement as follows:

for (factor = 2; target % factor != 0 && factor <= maxfactor;
factor = factor + 1)
;

This looks very strange as the loop body is empty: the test and iteration do all the work.

### Zero expressions

The "logical" expressions used in control statements or as arguments to && or || are considered to be "true" if they are not equal to zero. Hence in the statement:

if ( expression != 0 ) ...

The "= 0" is redundant and the following works just as well:

if ( expression ) ...

Thus our while() loop could be abbreviated to:

while ( target % factor && factor <= maxfactor )
factor = factor + 1;

## Every prime number up to 1000

Any { ... } block can have variables declared inside of it. We illustrate this by taking the guts of the above "prime number" example and enclosing it in a for() loop to find all the primes up to 1000:

//
// Find the lowest factor of the integers 2 to 1000, or say it is prime.
// The basic algoritm is to try every possible factor up to the square
// root of the number being looked at (the target)
//
#include <stdio.h>
#include <math.h>

int main() {
for (int target = 2; target <= 1000; ++target ) {
int factor, maxfactor;

maxfactor = sqrt(target); // Largest factor we need to try

factor = 2;
while ( target % factor != 0 && factor <= maxfactor )
++factor;

if ( factor > maxfactor )
printf("%d is prime\n", target);
else
printf("\t%d is not prime, its lowest factor is %d\n",
target, factor);
}
return 0;
}
Step through this code

In this example the variables factor and maxfactor can only be used inside the { ... } block they are declared inside of. Also, their values are not preserved between iterations of the while loop, they are "new" variables each time.

This example also illustrates that there are no restrictions on how while and if statements can be nested.