Slow prime finder

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 
#include 
#include 
#include 
#include 

#define LIMIT 2e6

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

    int i;
    for(i = 0; i  stop ) {
            break;
        }
    }

    for(x = primes[index]; x = (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;
}

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.

StackExchange Code Review Q#109804, answer score: 11