Not Finding Times of Prime Generation / Limited Generation

Question

This program is a c++ program that finds primes using the sieve of eratosthenes to calculate primes. It is then supposed to store the time it takes to do this, and reperform the calculation 100 times, storing the times each time. There are two things that I need help with in this program:

Firstly, I can only test numbers up to 480million I would like to get higher than that.

Secondly, when i time the program it only gets the first timing and then prints zeros as the time. This is not correct and I don't know what the problem with the clock is. -Thanks for the help

Here is my code.

#include <iostream>
#include <ctime>
using namespace std;

int main ()
{


    int long MAX_NUM = 1000000;
    int long MAX_NUM_ARRAY = MAX_NUM+1;
    int long sieve_prime = 2;
    int time_store = 0;
    while (time_store<=100)
    {
        int long sieve_prime_constant = 0;

        int *Num_Array = new int[MAX_NUM_ARRAY];
        std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
        Num_Array [0] = 1;
        Num_Array [1] = 1;


        clock_t time1,time2;
        time1 = clock();
        while (sieve_prime_constant <= MAX_NUM_ARRAY)
        {
            if (Num_Array [sieve_prime_constant] == 1)  
            {

                sieve_prime_constant++;
            }
            else
            {
                Num_Array [sieve_prime_constant] = 0;  
                sieve_prime=sieve_prime_constant; 
                while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant)  
                {
                    sieve_prime = sieve_prime + sieve_prime_constant;
                    Num_Array [sieve_prime] = 1;
                }
                if (sieve_prime_constant <= MAX_NUM_ARRAY)
                {
                    sieve_prime_constant++;
                    sieve_prime = sieve_prime_constant;
                }
            }
        }
        time2 = clock();
        delete[] Num_Array;
        cout << "It took " << (float(time2 - time1)/(CLOCKS_PER_SEC)) << " seconds to    execute    this loop." << endl;
        cout << "This loop has already been executed " << time_store << " times." << endl;
        float Time_Array[100];
        Time_Array[time_store] = (float(time2 - time1)/(CLOCKS_PER_SEC));
        time_store++;
    }


    return 0;

}

Answer 1

I think the problem is that you don't reset the starting prime:

int long sieve_prime = 2;

Currently that is outside your loop. On second thoughts... That's not the problem. Has this code been edited to incorporate the suggestions in Mats Petersson's answer? I just corrected the bad indentation.

Anyway, for the other part of your question, I suggest you use char instead of int for Num_Array. There is no use using int to store a boolean. By using char you should be able to store about 4 times as many values in the same amount of memory (assuming your int is 32-bit, which it probably is).

That means you could handle numbers up to almost 2 billion. Since you are using signed long as your type instead of unsigned long, that is approaching the numeric limits for your calculation anyway.

If you want to use even less memory, you could use std::bitset, but be aware that performance could be significantly impaired.

By the way, you should declare your timing array at the top of main:

float Time_Array[100];

Putting it inside the loop just before it is used is a bit whack.

---

Oh, and just in case you're interested, here is my own implementation of the sieve which, personally, I find easier to read than yours....

std::vector<char> isPrime( N, 1 );

for( int i = 2; i < N; i++ )
{
    if( !isPrime[i] ) continue;
    for( int x = i*2; x < N; x+=i ) isPrime[x] = 0;
}

Answer 2

This section of code is supposed to go inside your loop:

int *Num_Array = new int[MAX_NUM_ARRAY];
std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
Num_Array [0] = 1;
Num_Array [1] = 1;

Edit: and this one needs be in the loop too:

int long sieve_prime_constant = 0;

When I run this on my machine, it takes 0.2s per loop. If I add two zeros to the MAX_NUM_ARRAY, it takes 4.6 seconds per iteration (up to the 20th loop, I got bored waiting longer than 1.5 minute)

Answer 3

Agree with the earlier comments. If you really want to juice things up you don't store an array of all possible values (as int, or char), but only keep the primes. Then you test each subsequent number for divisibility through all primes found so far. Now you are only limited by the number of primes you can store. Of course, that's not really the algorithm you wanted to implement any more... but since it would be using integer division, it's quite fast. Something like this:

int myPrimes[MAX_PRIME];
int pCount, ii, jj;
ii = 3;
myPrimes[0]=2;
for(pCount=1; pCount<MAX_PRIME; pCount++) {
    for(jj = 1; jj<pCount; jj++) {
        if (ii%myPrimes[jj]==0) {
            // not a prime
            ii+=2; // never test even numbers...
            jj = 1; // start loop again
        }
    }
    myPrimes[pCount]=ii;
}

Not really what you were asking for, but maybe it is useful.