1

I'm implementing the sieve of eratosthenes algorithm in C++, and I've run into a problem. When I initialize my array to a very large value, like 1 million, it breaks because I'm allocating too large of an array to the stack. The answer in C would be to use malloc like this Sieve of Eratosthenes , but this solution does not work in C++ (to the best of my knowledge). Any ideas on how I could get this program to work with very large numbers by allocating the array in the heap instead of the stack? Thanks.

To see the problem I'm having, change the code below int integerList[1000], change 1000 to 1000000 or higher.

int main(void)
{
int userInput = 0;
int integerList[1000] = {};

cout << "Please pick a number to find all prime numbers " 
         << "from 2 to that number: " << endl;
//for the sake of writing out algorithm only, assume correct input
cin >> userInput;

//initialize array
for (int i = 2; i <= userInput; i++)
{
    integerList[i] = i;
}

//implementation of the algorithm
for (int i = 2; i < userInput; i++)
{
    if (integerList[i] != 0)
    {
        for (int j = 2; j < userInput; j++)
        {
            integerList[j*integerList[i]] = 0;
            if (integerList[i] * j > userInput)
            {
                break;
            }
        }
    }
}
for (int i = 0; i < userInput; i++)
{
    if (integerList[i] != 0)
    {
        cout << integerList[i] << " ";
    }
}
system("Pause");
return 0;
}
Community
  • 1
  • 1
trueCamelType
  • 2,198
  • 5
  • 39
  • 76
  • Related: you literally need an array of *bits* for a sieve of erath. The array need not contain the values of the very indices being used to access it in the first place. A prime `i` is known to be so (prime) if the flags array `sieve[i]` is set (nonzero). Short version: You could find all primes at or below some `N` using only `N/CHAR_BIT` *bytes* for your sieve; (and half of *that* if you exclude all even numbers past 2 before even starting). – WhozCraig Apr 02 '14 at 03:47
  • algorithm and primes tags are totally irrelevant to this question. Sieve of Eratosthenes in the title is irrelevant too. This I found out after actually reading the whole question. I had suggested an edit, removing the irrelevant tags, and making the title more relevant, which was accepted but it was then later rolled back (wtf? Did you even read Mr Rollback?) I again tried suggesting an edit, which rolled back to revision 2, which was rejected by My Rollback. Can someone actually read the question, and if they agree, roll it back to revision 2? Thanks. – RelevantTitlesAreBestTitles Apr 02 '14 at 14:31

1 Answers1

1

Allocating an array of size that large on the stack leads to stack overflow. To allocate it on the heap, you can do:

int *integerList = new int[1000000];

Or better, use a std::vector instead.

Yu Hao
  • 119,891
  • 44
  • 235
  • 294
  • Thanks for the quick answer, and it works perfectly. Can you tell me why you say using a vector would be better. I had read that arrays were faster, but I see more advanced programmers use vectors more. To narrow down the topic some, I don't mean to ask if vectors are better than arrays, or the other way around, I am just wondering why in this case a vector would be better than an array. – trueCamelType Apr 02 '14 at 03:57
  • 1
    @Slimmons In your example, the size is determined by the user input, not a compile time constant, that's a major reason to use `std::vector`, its size can grow dynamically, and it's also fast enough. – Yu Hao Apr 02 '14 at 08:35