C++, Prime Numbers and a windows error :(

[Banko]

I was trying to write a program that calculates primes using the sieve of eratosthenes, and well it works beatifully, except that if I want the prime numbers for anything greater then 500,000 I get an unknown exception. At first I thought I was hitting the limit of int's, but I even tried a long long data type and I still get the same thing? Can anyone help me?

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int max;
    cout << "Please enter a max prime number: ";
    cin >> max;
    int prime[max];
    for(int x = 0; x <= max; x++)
    {
            prime[x] = x;
    }
    prime[1] = 0;
    int curFactor = 2;
    while((curFactor * curFactor) <= max)
    {
        int mark = (curFactor + curFactor);
        while(mark <= max)
        {
                   prime[mark] = 0;
                   mark += curFactor;
        }
        curFactor++;
        while(prime[curFactor] == 0)
            curFactor++;                   
    }
    for(int x = 0; x <= max; x++)
    {
            if(prime[x] != 0)
            cout << prime[x] << " ";
    } 
    
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

[enlightenedby42]

Man, I had to write almost the exact same program last sem and it had the same limitations. Now that I think about it, a few other programs started returning weird results beyond a certain number. Might just be a built in limitation, but I'm very much not sure about that. I've heard that you have to start breaking numbers into peices at a certain point to work with them.

 

[mikeblas]

The problem is simply that you're trying to put too much data on the stack. Your declaration

    int prime[max];

will allocate four bytes for each of max primes. At 500,000, that's 2,000,000 bytes, which is more than you can put on the stack by default. I think you'll find that the program fails around 262,000 primes.

Further, I'm not sure how this code compiles in the first place. max isn't a constant expression, so how are you using it to declare the bounds of that array? Which compiler are you using?

Assuming the declaration does what you coded and not what the langauge says it should, then, you need to fix your program. You could increase the default stack size, or allocate the prime array dynamically. Or, you could look into a more efficient way of storing the flags for your sieve.

 

[Banko]

The problem is simply that you're trying to put too much data on the stack. Your declaration

    int prime[max];

will allocate four bytes for each of max primes. At 500,000, that's 2,000,000 bytes, which is more than you can put on the stack by default. I think you'll find that the program fails around 262,000 primes.

Further, I'm not sure how this code compiles in the first place. max isn't a constant expression, so how are you using it to declare the bounds of that array? Which compiler are you using?

Assuming the declaration does what you coded and not what the langauge says it should, then, you need to fix your program. You could increase the default stack size, or allocate the prime array dynamically. Or, you could look into a more efficient way of storing the flags for your sieve.

I'm just using Dev-C++ so it uses GCC to compile. Also since when does the variable that defines the size of the array has to be constant? It also doesn't fail at 262,000, but somewhere in between 500,000 and 600,000.

 

[Banko]

Also nm, I got it work by just using a char array and not actually storing the prime numbers in the array itself:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int max;
    cout << "Please enter a max prime number: ";
    cin >> max;
    char prime[max];
    for(int x = 0; x <= max; x++)
    {
            prime[x] = '1';
    }
    prime[1] = '0';
    int curFactor = 2;
    while((curFactor * curFactor) <= max)
    {
        int mark = (curFactor + curFactor);
        while(mark <= max)
        {
                   prime[mark] = '0';
                   mark += curFactor;
        }
        curFactor++;
        while(prime[curFactor] == '0')
            curFactor++;
    }
    for(int x = 1; x <= max; x++)
    {
            if(prime[x] != '0')
              cout << x << " ";
    } 
    
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

[mikeblas]

Also nm, I got it work by just using a char array and not actually storing the prime numbers in the array itself:

That just increases your limit; it doesn't fix the problem. If your linker gives you more stack space by default, then my estimates of space will be off; I'm assuming VC++, which has always given executables a default stack reserve of one megabyte.

If your int-based program was failing, then I would guess your stack reserve limit is two megs. Your new version should fail around two million. Of course, I'm assuming that memory comes from the stack -- your program shouldn't even compile, so I can't guess what the implementation is really doing.

Also since when does the variable that defines the size of the array has to be constant?

It doesn't have to be a constant; it has to be a constant expression. This has been true since 1985 or so. For a current reference, see section 5.2 of "The C++ Programming Language: Third Edition" by Bjarne Stroustrup:

The number of elements of the array, the array bound, must be a constnat expression.

In Section C.5 of the same book:

In places such as array bounds, case labels, and initializers for enumerators, C++ requires a constant expression.

Same thing in the C++ standard, section 8.3.4:

In a declarationT D where D has the form
D1 [constant-expressionopt]
and the type of the identifier in the declarationT D1 is “derived-declarator-type-list T,” then the type of the
identifier of D is an array type. T is called the array element type; this type shall not be a reference type, the
(possibly cv-qualified) type void, a function type or an abstract class type. If the constant-expression
(5.19) is present, it shall be an integral constant expression and its value shall be greater than zero. The
constant expression specifies the bound of (number of elements in) the array. If the value of the constant
expression is N, the array has N elements numbered 0 to N-1, and the type of the identifier of D is
“derived-declarator-type-list array of N T.”

Hopefully, you're depending on an explicit language extension and not a bug in the compiler. The right way to solve the problem you've got is to dynamically allocate the array using operator new.

Not storing the integer is a good idea. Now, you're using eight bits to store one bit of information; packing the value can make your program more space-efficient.

 

[Banko]

Heh, I myself figured out the 2 million limit before you posted that. I was doing this for fun, and when I took Intro to Comp Sci with C++ we never discussed the method of creating an array with new, but thanks! Now I know what you meant, and it seems to be work beatifully. Just like Java creates arrays (almost heh).

Say as a new question do you know how to make the time elapsed more accurate?

Here is my new code:

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

int main(int argc, char *argv[])
{
    time_t start,end;
    int max;
    
    cout << "Please enter a max prime number: ";
    cin >> max;
    time (&start);
    char * prime;
    prime = new char[max];
    for(int x = 0; x <= max; x++)
    {
            prime[x] = '1';
    }
    prime[1] = '0';
    int curFactor = 2;
    while((curFactor * curFactor) <= max)
    {
        int mark = (curFactor + curFactor);
        while(mark <= max)
        {
                   prime[mark] = '0';
                   mark += curFactor;
        }
        curFactor++;
        while(prime[curFactor] == '0')
        {
            curFactor++;
        }        

    }
    time (&end);
    double dif = difftime(end,start); 
    
    for(int x = 1; x <= max; x++)
    {
            if(prime[x] != '0')
              cout << x << " ";
    }
    cout << endl << "It took this many seconds to find the primes (Not Display Them): " << dif << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

[mikeblas]

I dug up the GCC docs, and it's an extension that they brought into C++ from C99. It's a very scary implementation; they just turn around and use alloca() for the allocation.

 

[mikeblas]

I don't know what GCC/G++ support for you. There's the clock() function from <time.h>, which will return a clock_t type. There's a macro named CLOCKS_PER_SEC which tells you how many clock_t counts you get per second.

If you want something Windows-specific, use QueryPerformanceCounter() and QueryPerformanceFrequency(). For a good sample, see the MSDN article
"How to Use QueryPerformanceCounter() to Time Code". These functions use the processor's performance counter, so it's hard to find anything more granular or accurate.

One way to speed up your code is to find the square root of max instead of computing (curFactor * curFactor) every time through that outer loop.

 

[Banko]

I don't know what GCC/G++ support for you. There's the clock() function from <time.h>, which will return a clock_t type. There's a macro named CLOCKS_PER_SEC which tells you how many clock_t counts you get per second.

If you want something Windows-specific, use QueryPerformanceCounter() and QueryPerformanceFrequency(). For a good sample, see the MSDN article
"How to Use QueryPerformanceCounter() to Time Code". These functions use the processor's performance counter, so it's hard to find anything more granular or accurate.

One way to speed up your code is to find the square root of max instead of computing (curFactor * curFactor) every time through that outer loop.

Thanks for the sqrt tip works great.