Ошибка во время выполнения, приводит к сбою .exe, и я не уверен, почему - PullRequest
Новая
       29

Ошибка во время выполнения, приводит к сбою .exe, и я не уверен, почему

1 голос
/ 12 января 2012

Могу предположить, что это как-то связано с работой с 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: Некоторые предпосылки того, что я пытаюсь сделать:

Я пытаюсь имитировать эту технику: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, в то время как я использую массив для хранения простого "простое ли это" 1 для да, 0 для нет.Конечная цель состоит в том, чтобы решить это:

What is the largest prime factor of the number 600851475143 ? Перечислено здесь: http://projecteuler.net/problem=3. Я просто работаю над простыми числами, а затем буду работать над простыми множителями.

Edit2:

Просмотрев ссылку на Википедию, которую я разместил, я понял, что у них есть puesdocode (пропущенный по этому поводу и придумал то, что у меня есть) и понял, что у него есть следующее примечание: большие диапазоны могут не полностью уместиться в памяти.В этих случаях необходимо использовать сегментированное сито, где за один раз просеиваются только части диапазона. [14]Для диапазонов, настолько больших, что простые сита не могут быть сохранены в памяти, вместо этого используются сита с эффективным использованием пространства, такие как сито Соренсона.Поэтому мне нужно будет придумать способ сделать это, используя метод «сегментированное сито».

Edit3:

Изменен массив для учета элемента [0], поэтому «проблема»фокусируется только на том, что объем памяти массива слишком велик для будущих ссылок;также сохранял массив как логическое значение вместо uint64.

Ответы [ 3 ]

5 голосов
/ 12 января 2012

Вы пытаетесь выделить массив uint64 длиной 600851475143. Для 8 байт uint64 это означает, что этот массив займет 600851475143*8byte, что примерно равно 4.5TB памяти. Даже если ваша система может выделить столько памяти (маловероятно), вы пытаетесь поместить ее в стек, размер которого обычно ограничен несколькими мегабайтами. Кроме того, вы пытаетесь записать в индекс number_in_question, в то время как последний индекс в массиве равен number_in_question-1.

3 голосов
/ 12 января 2012

Я предполагаю, что вы создаете стек, когда он пытается создать массив. Этот размер массива чрезвычайно велик и должен быть создан в куче, чтобы даже иметь шанс на успех.

0 голосов
/ 12 января 2012

В вашем массиве есть элементы "number_in_question", пронумерованные от 0 до number_in_question - 1. Но ваш цикл for попытается получить доступ к primes_array [number_in_question], который находится за пределами доступного пространства, если этот большой массив массива будет выделен вы.

Почему вы выделяете массив uint64 и сохраняете 0 или 1 в каждом элементе?

Редактировать: также, вы не можете выделить массив в стеке с переменным размером, как этот. Вы должны использовать новый, чтобы выделить это пространство в куче. Опять же, если предположить, что ваша система позволит вам выделить столько места.

...