CODEWITHSUNDEEP
c++sieve-of-eratosthenes
夢のの夢
夢のの夢

Reputation: 5846

program has stopped working?How to have int array size exceeding 1,000,000?

assignment: write a c++ program on sieve of eratosthenes and print out all the prime numbers between 1 and 1,000,000. I've realized that when I have a really large number such as 1,000,000, the program stops working and for small numbers such as 9,000, the program works perfectly fine. Is there a way to have 1,000,000 as integer array size?

#include <iostream>

using namespace std;

void sieve(int [], int num);

int main()
{
    int numOfElements;
    cout<<"please input number"<<endl;
    cin>>numOfElements;
    int primeArray[numOfElements];
    sieve(primeArray, numOfElements);
    return 0;
}

//prime number: any whole number greater than one and has factors of only the number itself and one.
void sieve(int prime[], int num){
    int i,j;
    for(int a=0;a<num;a++){
        prime[a]=a+1;
    }
    prime[0]=0;//we know 1 is not a prime;
    for(i=2;i<=num;i++){
        if(prime[i-1]!=0){
            cout<<i<<endl;
        }
        for(j=i*i;j<=num;j+=i){
            prime[j-1]=0;
        }
    }

}

Upvotes: 0

Views: 483

Answers (2)

Bathsheba
Bathsheba

Reputation: 234795

Being able to write int primeArray[numOfElements]; (this is called a variable length array) is a compiler extension: not part of standard C++. I do hope your compiler is warning you about this; if not then make sure the warning level is set correctly.

But that's a moot point in this case: attempting to allocate such a large array on the stack will fail. Stack sizes are limited to a size of an order of magnitude of a megabyte.

The best remedy is to use a std::vector which (i) is standard C++, and (ii) will allocate the memory on the heap.

If you must use an array, then you can use int* primeArray = new int[numOfElements]. Don't forget to free the memory using delete[], noting the brackets.

Upvotes: 5

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385295

int primeArray[numOfElements];

This is wrong!
Array dimensions must be known at compile-time.
They must be compile-time constants.

Use a std::vector<int> instead.

Upvotes: 3

Related Questions