Prime numbers are a popular topic in computer programming. It surprised me that I hadn’t yet plumbed primes on this blog, so I’m past due. And forget about the nerdy aspect of prime numbers. Of all the concepts in mathematics, primes are something most people understand.

In case you don’t understand a prime number, it’s a value that’s evenly divisible only by itself and the value one. So the number 5 is divisible by itself and one, but not 4, 3, or 2. Therefore, it’s a prime number. Another way to put it is that the only factors of 5 are itself and 1.

A factor is a number, an integer specifically, that divides evenly into another number. A challenge in programming might be to run a loop through a bunch of numbers to see which have have the most factors. This code uses the Power Of The Computer to help you run a factor hunt:

2020_10_24-Lesson-a.c

#include <stdio.h>

int main()
{
    int prime,x;

    prime = 2;
    while(prime<100)
    {
        /* find factors */
        printf("%d:",prime);
        for( x=2; x<prime; x++ )
        {
            if( prime%x == 0 )
            {
                printf(" %d",x);
            }
        }
        prime++;
        putchar('\n');
    }

    return(0);
}

This code uses nested loops to find factors for values 2 through 99. The outer while loop uses the prime variable to count. An inner for loop uses an if test to see which values, 2 through prime, are evenly-divisible and therefore factors:

if( prime%x == 0 )

Discovered factors are output at Line 16. Here is an abbreviated sample run:

2:
3:
4: 2
5:
6: 2 3
7:
8: 2 4
9: 3
10: 2 5
11:

88: 2 4 8 11 22 44
89:
90: 2 3 5 6 9 10 15 18 30 45
91: 7 13
92: 2 4 23 46
93: 3 31
94: 2 47
95: 5 19
96: 2 3 4 6 8 12 16 24 32 48
97:
98: 2 7 14 49
99: 3 9 11 33

Values such as 2, 3, 5, 7, and so on show no factors (well, other than one and themselves). These would be prime numbers, though the code doesn’t call them out specifically. Other numbers show valid factors, with the value 96 is evenly-divisible by 2, 3, 4, 6, 8, 12, 16, 24, 32, and 48. Wow.

I cover pulling out only prime numbers in next week’s Lesson. For now, the topic of factors has me obsessed. So I updated the code to count the number of factors for each value and output the results:

2020_10_24-Lesson-b.c

#include <stdio.h>

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

    prime = 2;
    while(prime<100)
    {
        /* find factors */
        count = 0;
        printf("%d:",prime);
        for( x=2; x<prime; x++ )
        {
            if( prime%x == 0 )
            {
                count++;
            }
        }
        printf("%d\n",count);
        prime++;
    }

    return(0);
}

A new variable, count, is added to track the number of factors for each value. Within the outer while loop, count is initialized to zero at Line 11: count = 0. For each factor found in the inner for loop, variable count is incremented: count++. After the for loop is complete, the value of count is output.

Here’s a sample run:

2:0
3:0
4:1
5:0
6:2
7:0
8:2
9:1
10:2
11:0

88:6
89:0
90:10
91:2
92:4
93:2
94:2
95:2
96:10
97:0
98:4
99:4

The highest number of factors I saw was 10, as shown above for 96 and 90, but other values had 10 as well. If you like, you can modify the code to scan the array for the highest values and output the “winners.”

Still, the topic for this and the next few Lessons is prime numbers. The code presented here can be modified further to pluck out only those prime values. You can try to do so on your own, or wait until I review the process in next week’s Lesson.