소수 생성기 오버플로? C++

Question

나는 eratosthenes의 체를 사용하여 소수에 대한 생성기를 쓰고 있습니다. 나는 521102 아래의 소수 생성에 노력을 기울 였지만 더 높은 숫자는 프로그램이 충돌하게 만든다. 여기 내 코드가있다.

#include <iostream> 
using namespace std; 

int main() 
{ 
    int long MAX_NUM = 1000000; 
    int long MAX_NUM_ARRAY = MAX_NUM+1; 
    int Num_Array [MAX_NUM_ARRAY]; 
    std::fill_n(Num_Array, MAX_NUM_ARRAY, 3); 
    int long sieve_prime = 2; 
    int long sieve_prime_constant = 0; 
    Num_Array [0] = 1; 
    Num_Array [1] = 1; 



    while (sieve_prime_constant <= MAX_NUM_ARRAY) 
    { 
     if (Num_Array [sieve_prime_constant] == 1) 
     { 

      sieve_prime_constant++; 
     } 

     else 
     { 
     Num_Array [sieve_prime_constant] = 0; 
     sieve_prime=sieve_prime_constant; 
      while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant) 
      { 
       sieve_prime = sieve_prime + sieve_prime_constant; 
       Num_Array [sieve_prime] = 1; 
      } 

      if (sieve_prime_constant <= MAX_NUM_ARRAY) 
      { 
       sieve_prime_constant++; 
       sieve_prime = sieve_prime_constant; 
      } 
     } 
    } 
return 0; 
} 

MAX_NUM을 1000000으로 입력했는데 작동하지 않습니다. 그러나 전에 말했듯이 521102 이하의 숫자가 효과가 있습니다. 높은 숫자를 테스트 할 수 있어야합니다. 내 문제는 무엇이며 어떻게 해결할 수 있습니까?

고맙습니다.

감사합니다. 나는 동적으로 배열을 할당하는 해결책을 시도했다. 그것은 어느 정도까지 잘 작동했습니다. 내가 프로그램을 실행할 때 약 500 백만에 MAX_NUM을 설정 한 후 나는 무엇을()

은 '표준 : : bad_alloc 뿐이다' 의 인스턴스를 던지는 후 호출 종료 ...이 오류를 얻을 : 표준 : : bad_alloc 뿐이다

이 응용 프로그램 비정상적인 방식으로 런타임을 종료하도록 런타임에 요청했습니다. 자세한 내용은 응용 프로그램 지원 팀에 문의하십시오.

500million의 지붕을 허용해도 좋지만 높을수록 좋습니다. 다른 아이디어가 있습니까?

Answer 1

아마 스택을 부숴 버리기 때문일 수 있습니다. 배열을 main() 함수 밖으로 이동하는 방법은 어떻습니까?

int Num_Array [MAX_NUM_ARRAY];

당신은 그것을 할당해야합니다

#define MAX_NUM = 1000000; 
#define MAX_NUM_ARRAY (MAX_NUM + 1) 
int Num_Array[MAX_NUM_ARRAY]; 

int main() 
{ 
    // etc. 
    return 0; 
} 

Answer 2

는 Windows에있어 가정하면, 당신의 스택이 너무 작습니다 (기본적으로 1메가바이트)는 스택 프레임에서 다음 변수를 맞게 힙 :

int *Num_Array = new int[MAX_NUM_ARRAY]; 
... 
delete[] Num_Array; 

Answer 3

당신이 std::fill_n를 사용하는 것은 ++ 실제로 C를 작성하고 표시하지 C. 사실

int 배열 대신 실제 bool 배열을 사용하여 프로그램의 메모리 소비를 크게 줄일 수 있습니다. C++을 사용하고 있으므로 std::vector<bool>을 사용하여 부울 배열을 가져올 수 있습니다. bool[n]과 달리 std::vector<bool>(n)은 n 비트 (은 8n 비트를 사용하거나 컴퓨터/컴파일러에서 가장 작은 정렬이 무엇이든간에 사용자의 Num_Array[n]은 실제로 32 비트 정수를 사용하여 부울 값을 저장하기 때문에 32n 비트를 차지합니다).

다른 의견은이 값을 스택 대신 힙에 저장하는 것이 좋습니다. std::vector<bool>이 자동으로 처리됩니다.