Numbers with only two factors, one and themselves, are prime. One way to discover which numbers are prime in a computer program is to plow through all the factors.

In last week’s Lesson, I presented code that counts the number of factors for a range of values. When the number of factors is zero (excluding 1 and the value itself), the value is prime. The following code makes an improvement to the examples from last week’s Lesson by adding a TRUE/FALSE (Boolean) variable isprime to determine prime numbers:

2020_10_31-Lesson-a.c

#include <stdio.h>

#define TRUE 1
#define FALSE 0

int main()
{
    int prime,x,isprime;

    prime = 2;
    while(prime<100)
    {
        isprime = TRUE;
        printf("%d:",prime);
        for( x=2; x<prime; x++ )
        {
            if( prime%x == 0 )
            {
                isprime=FALSE;
                break;
            }
        }

        if( isprime )
            puts("Prime");
        else
            puts("Not prime");

        prime++;
    }

    return(0);
}

Variable isprime is declared as an int, not a _bool, still its use is the same. The variable is initialized to TRUE at Line 13. Line 17 tests for factors:

if( prime%x == 0 ))

If the result of prime%x is equal to zero, a factor has been found and the value of isprime is set to FALSE, then the loop breaks (Line 20). But when a value stored in variable prime lacks factors, isprime remains TRUE and an if-else structure outputs the proper results, shown here:

2:Prime
3:Prime
4:Not prime
5:Prime
6:Not prime
7:Prime
8:Not prime
9:Not prime
10:Not prime
11:Prime

88:Not prime
89:Prime
90:Not prime
91:Not prime
92:Not prime
93:Not prime
94:Not prime
95:Not prime
96:Not prime
97:Prime
98:Not prime
99:Not prime

Of course, this list is difficult to sift through. It’s more of a subtle update to the code from last week’s Lesson. In the following update, the code outputs only found prime numbers:

2020_10_31-Lesson-b.c

#include <stdio.h>

#define TRUE 1
#define FALSE 0

int main()
{
    int prime,x,isprime;

    prime = 2;
    while(prime<100)
    {
        isprime = TRUE;
        for( x=2; x<prime; x++ )
        {
            if( prime%x == 0 )
            {
                isprime=FALSE;
                break;
            }
        }

        if( isprime )
            printf(" %d",prime);

        prime++;
    }
    putchar('\n');

    return(0);
}

The code limits output to a single printf() statement at Line 24, showing only prime numbers from 2 through 99:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

I’m sure the output appeared immediately on your computer; the code doesn’t really work hard to pump out the first several prime numbers. For a thrill, change the looping value at Line 11 to 1000000 (one million) and see how long those last few values take to output.

This code is just one way to hunt prime numbers. In next week’s Lesson I show a different approach, one that is optimized slightly.