More Efficient Prime Number Calculations

A long time ago, I looked at one of my prime number hunting programs, such as the one demonstrated in last week’s Lesson. I thought, “How can I make this program more efficient?” It’s something all programmers should do.

First I figured that only prime numbers themselves matter in the prime number hunt.

For example, if you have the value n, you can check to see whether it’s divisible by all the values 2 through n or you can just check to see whether it’s divisible by prime numbers from 2 to n. After all, the in-between values such as 4, 10, 15, and so on already have prime number factors. So these values can be merrily skipped as you check for factors of n.

Further, you don’t really need to check for factors greater than n/2. These larger factors probably don’t divide cleanly into n anyhow, so why bother doing the math? In fact, I’m sure there’s some mathematical theory on what fraction of a number can contain the largest factor of that number. At some point, checking lager values is a waste of time.

I’m no mathematician. In fact, what kept me from computers in college was a fear of math; I’m terrible at it. My university math grades are horrid. Yet, I enjoy ruminating on the topic, which is what got me going with this prime number hunt code:

2020_11_07-Lesson.c

#include <stdio.h>

#define COUNT 100
#define TRUE 1
#define FALSE 0

int main(void)
{
    int n,i,c,a,index,isprime;
    int primes[COUNT];
    
    printf("The first %d primes:\n\n",COUNT);

/* initialize */
    index = 0;                        /* set index for array */
    primes[index] = 2;                /* 2 is the first prime */
    a = 1;                            /* set counter */

/* calculate the first COUNT prime numbers */
    while(index<COUNT)
    {
        n = primes[index] + a;        /* next value after last prime */
                                      /* is n prime? */
        isprime=TRUE;                 /* Assume it is prime for now */

        for(i=0;i<index;i++)          /* divide n by recorded primes */
        {
            c = n/primes[i];
            if(n == primes[i]*c)      /* if TRUE, n is not prime */
            {
                isprime=FALSE;
                break;                /* this saves time */
            }
            if(primes[i] > (n>>1))    /* eliminate divisors */
                break;                /* greater than n/2 */
        }

        if(isprime)                   /* the value is prime */
        {
            index++;
            primes[index] = n;        /* add it to the array */
            a = 1;                    /* set to next number */
        }
        else
            a++;                      /* jump to text next value */
                                      /* the value of a indicates the
                                         space between primes. It will
                                         never be <2 but can get quite
                                         large */
    }

/* display the results */
    for(i=0;i<COUNT;i++)
        printf("%5d\t",primes[i]);
    printf("\n\n");

    return 0;
}

Unlike last week’s examples, this code tracks found prime numbers in in an array, primes[] declared at Line 10. It’s initialized with value 2 at the zeroth element (Line 16), which saves time with other calculations.

In the while loop, potential prime values are stored in variable n. This value is initialized to the next integer after the previously-stored prime number at Line 22: n = primes[index]+a. This choice saves time over starting each new hunt at a lower number.

Next, the program runs a for loop that divides n by values stored in the primes[] array at Line 28. Tests are made to determine whether the value is cleanly divisible. If so, the number isn’t prime and the for loop breaks.

Found primes are added to the array at Line 41.

The code hunts for the first 100 primes, which are output:

The first 100 primes:

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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

You can modify the code to output a greater span of prime numbers: Change the defined constant COUNT to something larger. Unlike my other examples, this code runs a lot faster because it’s not churning through every value from 2 to n for each cycle.

I know plenty of other prime number hunting programs are possible. Perhaps you can venture out and write a unique one on your own. Doing so is great coding practice.

Leave a Reply