Project Euler #7 in C: find 10001st prime using something like Sieve of Eratosthenes

Question

I've gotten a solution for Project Euler #7 in C (find the 10,001st prime). I came up with the very simple algorithm myself (from what I can tell it's similar, if not identical, to the Sieve of Eratosthenes).

#include <stdio.h>

#include <stdlib.h>

long prime_finder(int amount_of_primes);

int main(void)
{
int amount_of_primes = 0;

printf("How many primes would you like?\n");
scanf("%d", &amount_of_primes);

printf("%d: %ld\n", amount_of_primes, prime_finder(amount_of_primes));

return 0;
}

long prime_finder(int amount_of_primes)
{
int total_primes_found = 0;

long * primes = malloc(sizeof(long) * amount_of_primes);

for(int i = 0;i < amount_of_primes; i++) //set everything to 0
{
    primes[i] = 0;
}

for(long i = 1; total_primes_found < amount_of_primes;i++) //find the primes
{
    if(i<14) //cheat a little for the first primes
    {
        switch (i)
        {
            case 1:
                break;

            case 2:
                primes[total_primes_found++] = 2;
                break;

            case 3:
                primes[total_primes_found++] = 3;
                break;

            case 5:
                primes[total_primes_found++] = 5;
                break;

            case 7:
                primes[total_primes_found++] = 7;
                break;

            case 11:
                primes[total_primes_found++] = 11;
                break;

            case 13:
                primes[total_primes_found++] = 13;
                break;

            default:
                break;
        }
    }

    else //if it is a larger number
    {
        if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 
|| i % 7 == 0 || i % 11 == 0 || i % 13 == 0) /*makes the program a little quicker if the
*current number divides by a low number like 2 or 3*/
        {
            goto End;
        }

        else
        {
            for(int j = 0; j < total_primes_found; j++) //the brute force part of the program
            {
                if(i % primes[j] == 0)
                {
                    goto End;
                }
            }

            primes[total_primes_found++] = i;
        }

        End:;

    }
}

for(int i = 0 ; i < amount_of_primes - 1 ; i++)
    printf("%d: %ld\n", i+1, primes[i]);

return primes[amount_of_primes - 1];
}

Answer 1

Your code is using trial division (i % primes[j] == 0) and thus it is not at all similar to the Sieve of Eratosthenes - or any prime sieve, for that matter.

The core idea of prime sieves is that you have some sort of array with a flag for each of the candidate numbers - the sieve - and that all the non-primes in that array get struck off in some fashion so that whatever is left must be prime.

The hallmark of Eratosthenean sieving is the avoidance of multiplication and/or division during the striking-off process; multiples of a number are enumerated by repeated addition of that number. That's why it can be several orders of magnitude faster than the alternatives.

There's nothing wrong with trial division as such, as long as you find it fast enough for your purposes. Had the Euler problem description asked for the 100,000,001st prime then things would look different, though, and you'd need a lot of patience for approaches based on trial division. So much so that you'd be faster programming a nice sieve instead of waiting for the trial divider to finish...

Next time, start with the simplest, most straightforward implementation of your idea and leave out the supposed optimisations. Don't start 'optimising' until you have proof that it's necessary, and keep optimisations only if the measured improvement significantly outweighs the resulting uglification of your source code. If you do some measurements then you'll find that only appreciable effect of your current 'optimisations' is to make the code unreadable.

Starting with the simplest, cleanest rendering of your algorithm might help you avoid mistakes like trial dividing by the primes 2 .. 13 twice (first explicitly in a branch statement, then again implicitly when checking against the array of found primes).

Also, in order to prove the compositeness of a number you only need to check potential factors up to the square root of the number. You are checking all primes less than that number (i.e. all primes found so far), which is a lot more than necessary.

Note: explicitly trial-dividing by a handful of the smallest primes is indeed a valid optimisation that can also be found in industrial-strength code. It works because dividing by constants enables compilers to pick more efficient means than actual division, like using multiplication and shifting, or testing bit 0 for computing x % 2. However, like all optimisations it needs not only the proof of validity but also the proof of necessity in order to make the cut.