C++에서 배열 초기화시 Seg 오류 (프로젝트 오일러 번호 3)

Question

그래서 프로젝트 오일러 문제를 가장 큰 요인으로 해결하기 위해 프로그램을 작성하려고합니다. 코드가 구조적으로 정확하다는 것을 알고 있습니다. 예 그들이주고 있다는 13,195), 내가 입력 우리가 생각하는 숫자 인 해결하기 세그먼트 오류를 ​​수신 유지를 포함하여 작은 숫자에 대한 정답, 600851475143. 코드는 다음과 같다 :

#include <stdio.h> 
#include <math.h> 

main(){ 
    int number,a,b,c,i,j,n,gpf; 
    printf("Input number to analyze: "); 
    scanf("%d",&number); 
    a = number/2; 
    printf("%d\n",a); 
    int* primesieve = new int[a+1];    /*IMPORTANT LINE*/ 
    for (i=0;i<a+1;i++){ 
     primesieve[i] = 1; 
    } 
    for (j=2;j<=a;j++){ 
     if (primesieve[j] == 1){ 
      for (c=2;j*c<=a;c++){ 
       primesieve[j*c] = 0; 
      } 
     } 
    } 
    for (n=2;n<=a;n++){ 
     b = number/n; 
     printf("%d\n",b); 
     if (number % n == 0){ 
      if (primesieve[b] == 1){ 
       gpf = b; 
       n = a+1; 
      } 
     } 
    } 
    delete[] primesieve; 
    printf("The greatest prime factor of %d is %d.\n",number,gpf); 
} 

문제점은 프라임 시브 (prime sieve)에 대한 배열의 초기화에서 온 것입니다. 왜냐하면 그 이후의 모든 라인을 생략했기 때문에 문제가 발생했기 때문입니다. 원래 다음 코드를 사용하여 배열을 선언했습니다.이 코드는 1,000 만 개의 낮은 값에 대해 세그먼트 화 오류를 반환했습니다.

int primesieve[a+1]; 

나는 동적 배열 할당의 변경을 산출이 사이트에 솔루션을 검색하지만,이 동안 분명히 상당히 큰 값을하지 않았다, 천만의 문제를 해결했다. 다른 해결책으로는 malloc()을 사용하거나 main() 외부에 배열을 정적으로 선언하는 것에 대해 언급 한 적이 있지만 솔직히 malloc()을 거의 언급하지 않은 채 솔라리스 입문 프로그래밍 클래스를 이해하지 못했으며 선언문 main()에 포함될 필요가있는 배열의 배열. (참조 용 : Segmentation Fault While Creating Large Arrays in C 및 Seg Fault when initializing array) 상당히 간단한 문제이지만, 비교적 새로운 프로그래머이므로 메모리 할당에 대한 이해가 부족하므로 다른 솔루션에 대한 제안, 해결책 또는 설명이 부족합니다. 나는 크게 감사 할 것이라고 알았다.

Answer 1

사용자의 경험은 컴파일러의 물리적 한계와 정밀도와 관련이 있습니다. 대부분의 시스템에서 스택이 아니라 힙에 비해 크기가 제한되어 있기 때문에,

int primesieve[a+1]; 

빨리 실패 스택에 배열을 할당 첫 번째 시도.

힙

int* primesieve = new int[a+1]; 

에 할당하면 더 많은 공간을 제공하지만, 당신은 여전히 ​​주소 지정 가능 메모리의 제한이 있습니다. 이제 600851475143은 2로 나누더라도 꽤 큰 숫자입니다. int의 크기가 4 바이트라고 가정하면 실제로 많은 메모리를 처리 할 수 ​​있는지 궁금 할 수 있습니다. 32 비트로 2^32 = 4294967296 바이트를 지정할 수 있습니다.

Answer 2

오버플로!

메모리에 어레이 크기 600851475143을 할당 할 수 없습니다. 32 비트 시스템에서는 4,476 GB이 필요합니다.

Answer 3

600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB 

즉, 5TB RAM이 없으면이 코드는 항상 중단됩니다.

체에 비트 맵을 사용하면 조금 더 견딜 수 있습니다. 예를 들어, 숫자 당 1 비트를 사용하고 짝수 매핑이 아니라면 600851475143/8/2 = 35GB의 RAM이 필요합니다. 여전히 많이 있지만, 하드웨어에 돈이 있다면 가능합니다.