[C] Optimal prime generators experiment

[Freak]

A while ago I remembered a time about 5 years ago in high school when some friends and I were writing prime number generators in C++ and seeing who could make theirs the fastest. Since I've been picking up some C in my spare time I thought I'd try that again!

My first version involved checking only odd numbers, and dividing them by all of the odd numbers up to their square roots. It also just checks up to 2 million. It's just an arbitrary upper limit that I set at the time.

Code: (c) [Select]

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[]){
    int i = 1;
    int e;
    outer_loop:
        while(i<2000000){
            i+=2;
            for(e = 3;e<sqrt(i);e+=2){
                if(!(i%e)){
                    goto outer_loop;
                }
            }
            //printf("%d\t", i);
        }
    return 0;
}

Now before you yell at me for using goto let me explain myself! I changed it to this while I was optimizing it. Originally it was nested loops, but I didn't have an easy way to do a "continue" for the outer loop. I was using break in the inner loop and needed to use a variable as a check if a number was prime or not. The whole idea of this was to try to make it as fast as I could. This goto statement makes it act exactly how it did before, except I didn't need a checking variable that would slow down the program (albeit by an almost immeasurable amount).

This program generally runs in about 5 seconds.

Now the problem with this program is that it is a shitty algorithm. It's definitely better than what we did in high school when we divided every number--including even numbers--by every number before its half. The reason that this algorithm is still slow is because lets say I'm checking 41 or something.
41%3 != 0
41%5 != 0
41%6 != 0
There is NO number that is divisible by 6 and isn't divisible by 3. This program checks multiples of prime numbers, which is pointless. Rather, it should only check for even division by prime numbers because every non-prime is divisible by at least 1 prime beneath it.

I realized this after a while, and that's when I got discouraged for a while. C doesn't have dynamically expanding arrays, so I can't just add every newly discovered prime to an array. I thought about implementing a linked list or something, but I don't know C well enough to do that yet.

Just recently I realized a solution that isn't ideal but would work. I would initialize the array to be large enough for 148993 elements. That's the number of prime numbers between 2 and 2 million.

Code: (c) [Select]

#include <stdio.h>

int main(int argc, char *argv[]){
    int i = 3;
    int e;
    int count = 1;
    int primes[148932] = {3}; //set the array size to the number of primes before the upper limit.
    outer_loop:
        while(i<2000000){
            i+=2;
            for(e = 0;(primes[e]*primes[e])<=i;++e){
                if(!(i%primes[e])){
                    goto outer_loop;
                }
            }
            //printf("%d\t", i);
            primes[count] = i;
            ++count;
        }
    return 0;
}

This one isn't ideal because I can't just change the upper limit whenever to see how fast it is for a different number of primes. It requires you to know ahead of time how many primes there are in your interval (meaning you already ran a prime number generator).

This one ran in about 3.2 seconds until my friend suggested I change

Code: (c) [Select]

primes[e]<=sqrt(i)
to

Code: (c) [Select]

(primes[e]*primes[e])<=i
after which it runs in about .2 seconds.

It turns out that determining square roots is very slow because the algorithm used requires doing a bunch of loops until they approximate it.

I wrote a final version that takes a command line argument for how many primes you want to generate. So instead of finding them all in an interval it finds a specific number of them. This sort of avoids the issue with the last one where you can't experiment with different intervals, but not completely because it abandons the interval model.

Code: (c) [Select]

#include <stdio.h>

int main(int argc, char *argv[]){
    int num = atoi(argv[1]);
    int i = 3;
    int e;
    int count = 2;
    int primes[num];
    primes[0] = 2;
    primes[1] = 3;
    outer_loop:
        while(count<num){
            i+=2;
            for(e = 1;(primes[e]*primes[e])<=i;++e){ //e=1 because primes[0]==2 and i will never be even.
                if(!(i%primes[e])){
                    goto outer_loop;
                }
            }
            primes[count] = i;
            ++count;
        }
    /*for(i = 0;i<num;++i){
        printf("%d\t", primes[i]);
    }*/
    return 0;
}

This one generally runs at the same time as the last one if you run "prime3.exe 148993" because there weren't any real changes to the algorithm itself.


I still might try a linked list implementation so that I can compare that, but I'd assume that it's slower than my second version.

If you have any optimization suggestions, I'd LOVE to hear them! This is pretty fun for me because it reminds me of the fun I had in that class goofing around with my friends.

[HTH]

Three Words: Sieve of Eratosthenes

I quickly wrote the whole (modolus by every prime smaller than) vs (sieve) and this is the results:

HOST:~/Desktop$ g++ sieve.cpp
HOST:~/Desktop$ time ./a.out 5000000
real    0m0.074s
user    0m0.069s
sys    0m0.005s
HOST:~/Desktop$ g++ modolus.cpp
HOST:~/Desktop$ time ./a.out 100000
real    0m0.196s
user    0m0.200s
sys    0m0.000s

So even with the Sieve doing 500 times as large of a dataset, the modolus method is 3x slower.

I'd look into it if I were you Or I can just tell you that it has a large memory tradeoff and you might figure it out

[reqq456]

Can you share the code for your sieve?

[kenjoe41]

Stop being lazy. Here is the wikipedia page: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and here is the forum members trying there hands at it. My solution there needs some cleaning up but code yours and post it there: https://evilzone.org/weekly-challenge/challenge-17-sieve-of-eratosthenes/

But, this is alittle old method for generting prime irrespective of the fact that it is still quite faster than alot of other methods. Look into Sieve of Atkins: http://en.wikipedia.org/wiki/Sieve_of_Atkin

[HTH]

Can you share the code for your sieve?

Sure, it's kind of a piece of shit, I literally wrote it to show you the speed difference and as such there are still optimizations to be made :p In fact im pretty sure you can cause it segfault pretty easily, but thats the general idea down there :p

Code: [Select]

#define U_LIMIT 65534 //Keep it below 65535 chap
typedef unsigned int bigInt; //OR change this!

bigInt findPrimes()
{
    //Allocate
    bigInt primeCount = 1;
    bigInt tryCount = 2;
    unsigned char trialArray[U_LIMIT];
   
    //Sieve!
    while (tryCount < U_LIMIT)
    {
        //Mark off all multiples
        for (bigInt i = tryCount; i <= U_LIMIT; i += tryCount) trialArray[i] = 'M';
       
        //Locate next not-marked off number
        for (bigInt i = tryCount; i <= U_LIMIT; i++)
            if (trialArray[i] != 'M')
            {
                tryCount = i;
                primeCount++;
                goto outerLoop;
            }
        tryCount = U_LIMIT;
        outerLoop:;
    }
    return primeCount;
}

[Freak]

Thanks, HTH, for telling me about that! I went ahead and wrote my own implementation:

Code: (c) [Select]

#include <stdio.h>
#define upper 2000000
int nums[upper] = {0}; //0 means prime

int main(int argc, char *argv[]){
    unsigned long i, e;
    for(i = 3;;i+=2){
        if(!(nums[i])){
            printf("%d\t", i);
            if((i*i)>upper){
                i+=2;
                break; //After (i*i)>upper there are no composites that weren't covered by the earlier primes
            }else{
                for(e = 2*i;e<upper;e+=i){ //Set multiples to composite
                    nums[e] = 1; //1 means composite
                }
            }
        }
    }
    for(;i<upper;i+=2){ //Same as before but without eliminating composites
        if(!(nums[i])){
            printf("%d\t", i);
        }
    }
    return 0;
}

Which takes about .095 to calculate up to 2 million. That's not quite as much as an increase as yours showed though. Any of you see something I might have done poorly? Like I said, I'm pretty new to C.

Should I go ahead and post this to challenge 17 too?

Kenjoe41, I bookmarked the wiki page for the Sieve of Atkin so thanks for that! That page also talks about a sieve that Euler made, so I'll probably give both of those a go and post them here when I finish them.

[HTH]

Nothing jumps out a me, it probably because you print them out.

There`s also machine differences to be taken into account, the machine I ran that on was clocked to 5.0(4.9 maybe) ghz and has high speed everything. That could easily account for the differences as well if your machine isnt clocked as high.

[Freak]

Oh, I just forgot to comment out the print statements  for my post, but when I tested it for speed it was without printing. It takes like 8 seconds with printing haha.
Computer speed is probably it then. Thanks