Slow prime finder

Question

This program runs in about 1.65 seconds on a 1.65GHz dual core processor.

I compile it with:

gcc -Wall -o ./program ./program.c -lm

Are there any optimizations I can use to speed this up, or is it already going about as fast as possible on this machine?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>

#define LIMIT 2e6

int is_prime(int num, int* primes, int index)
{
    double stop = sqrt(num);
    int x;

    int i;
    for(i = 0; i <= index ; ++i) {
        if( !(num%primes[i]) ) {
            return 0;
        }

        if( primes[i] > stop ) {
            break;
        }
    }

    for(x = primes[index]; x <= stop; x += 2) {
        if( !(num%x) ) {
            return 0;
        }
    }

    return 1;
}

int main(void)
{
    double time_spent;
    clock_t begin, end;
    begin = clock();

    int size = 8;
    int* primes;
    primes = (int*)malloc(size*sizeof(int));
    assert(primes);

    int i = 0;
    primes[i++] = 2;

    unsigned long long int sum = 2;

    int candidate = 3;
    while( candidate < LIMIT ) {
        if( is_prime(candidate, primes, i-1) ) {
            if( i >= (size-1) ) {
                size *= 2;
                primes = (int*)realloc(primes, size*sizeof(int));
                assert( primes );
            }

            primes[i++] = candidate;
            sum += candidate;
        }

        candidate+=2;
    }

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("%i primes sum to %llu in %f seconds\n", i-1, sum, time_spent);

    return 0;
}

Answer 1

Compilation

First of all, you could simply add -O3 to your command line. There's no point in timing with optimizations off. That drops you from (on my box) 0.21s to 0.17s.

Algorithm

It's good that you're only testing primality against primes. However, you have this extra loop:

for(x = primes[index]; x <= stop; x += 2) { ... }

We will never return 0 in that loop. If a number is not prime, it is going to be divisible by a prime less than it. We would have already found all of those... so there is simply no extra divisor we have yet to find. You can delete it without loss of functionality.

Also, typically we pass in the length of the array and name is as such:

int is_prime(int num, int* primes, int num_primes)

So that the loop becomes:

for(i = 0; i < index ; ++i) {

Better Algorithm

But ultimately, this isn't a great algorithm for finding all the primes. The most common would be the Sieve of Eratosthenes. We make an array up front for our candidates:

char* is_prime = (char*)malloc(LIMIT * sizeof(char));
memset(is_prime, 1, LIMIT); // everything is prime to start

And then cross off all the multiples:

for (i=3; i < LIMIT; i += 2) {
    if (is_prime[i]) { 
        // i is definitely prime
        for (j=i*i; j<LIMIT; j+=i) {
            // j is definitely NOT prime
            is_prime[j] = 0;
        }
    }
}

You can sprinkle in your prime count and sum in there as appropriate, this is just the general idea. This runs about 10x faster than checking divisibility for each prime.

Answer 2

! (num % x) is considered awful style. So bad that newer languages like Swift make it illegal. Write "num % x == 0".

What's really slow is mixing integer and floating point numbers. The comparison "if( primes[i] > stop)" is really, really slow, because stop is a double, and this forces a slow conversion of primes [i] from int to double. Changing stop to be an int should be significantly faster.

Now let's get complicated. I'd want a much simpler loop like

for (i = 0; i < index; ++i)
    if (num % primes [i] == 0)
        return 0;

return 1;

How can we achieve this? You must check all primes p where p^2 <= num. So you want to have a value index where primes [index - 1]^2 <= num, but primes [index]^2 > num.

So in your caller create a new variable

int count_divs = 0;

Before you call is_prime you make sure that count_divs is big enough:

while (primes [count_divs] * primes [count_divs] <= candidate)
    ++count_divs;

And then you pass count_divs instead of i, and in is_prime, you just execute the loop for (i = 0; i < index; ++i) without checking the size of the primes at all.