Runtime error, makes my .exe crash and I am not sure why

Question

I can take a guess that it has something to do with working with the unsigned long long int.

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long int uint64;

int main(int argc, char *argv[])
{



    uint64 number_in_question = 600851475143LL;

    long double sqrt_in_question = sqrt(number_in_question);
    bool primes_array[number_in_question+1];



    for (uint64 i = 0; i <= number_in_question; i++) {
        primes_array[i] = true;
    }

    for (uint64 i = 2; i <= sqrt_in_question; i++) {
        if(primes_array[i] == true) {
            // for every multiple of this prime, mark it as not prime
            for (uint64 ii = i*2; ii <= number_in_question; ii += i) {
                primes_array[ii] = false;           
            }
        }
    }   

    for (uint64 i = 0; i <= number_in_question; i++) {
        if(primes_array[i] == true)
        cout << i << ", ";
    }


    system("PAUSE");


    return EXIT_SUCCESS;
}

Edit1: Some background of what I am trying to do:

I am trying to mimic this technique: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes while I am using an array to store a simple "is it prime" 1 for yes, 0 for no. The end goal is to solve this:

What is the largest prime factor of the number 600851475143 ? Listed here: http://projecteuler.net/problem=3. I am just working on the primes and then will work on the prime factors.

Edit2:

Upon looking at the Wikipedia link I posted, I realized they have puesdocode (skipped over that and came up with what I have) and realized that had this note: Large ranges may not fit entirely in memory. In these cases it is necessary to use a segmented sieve where only portions of the range are sieved at a time.[14] For ranges so large that the sieving primes could not be held in memory, space-efficient sieves like that of Sorenson are used instead. Therefore I will have to think of a way to do this using a "segmented sieve" method.

Edit3:

Changed the array to account for the [0] element so the "issue" is only focused on the array memory size being too large for future references; also stored the array as a bool instead of a uint64.

Answer 1

You are trying to allocate an uint64 array of length 600851475143. For 8 byte uint64 that means this array will take up 600851475143*8byte which is roughly 4.5TB of memory. Even if your system can allocate that much memory (unlikely) you are trying trying to put it on the stack which has typically a size bound to only a few MB. Furthermore you are trying to write to index number_in_question, while the last index in the array is number_in_question-1.

Answer 2

I would assume your are blowing the stack when it attempts to create the array. That size of array is tremendously large and would have to be created on the heap to even have a chance of succeeding.

Answer 3

Your array has "number_in_question" elements, numbered 0 to number_in_question - 1. But, your for loop will try to access primes_array[number_in_question], which is outside the available space, if that large of an array will even be allocated to you.

Why are you allocating an array of uint64 and storing either 0 or 1 in each element?

Edit: also, you can't allocate an array on the stack with a variable size like that. You'd have to use new to allocate that space on the heap. Again, assuming your system will allow you to allocate that much space.