매우 큰 체에 대해 어떻게 메모리를 예약 할 수 있습니까?

Question

최대 100,000,000까지 체로 처리하여 소수를 생성하려고하지만이 범위의 부울 배열을 선언하면 프로그램이 비정상적으로 종료됩니다. 이것은 내 코드입니다.

long long i,j,n; 
bool prime[100000000+1]; 
prime[1]=prime[0]=false; 
for(i=2;i<=100000000;i++){ 
    prime[i]=true; 
} 
for(i=2;i<=100000000;i++){ 
    if(prime[i]==false){ 
     continue; 
    } 
    for(j=i*2;j<=100000000;j+=i){ 
     prime[j]=false; 
    } 
} 

이 문제를 어떻게 해결할 수 있습니까?

Answer 1

변수는 정적 메모리, 자동 메모리, 동적 메모리의 세 가지 메모리 영역에 저장할 수 있습니다. 자동 메모리 (정적이 아닌 지역 변수)는 크기가 제한되어 있으며이를 넘어서서 프로그램이 중단되었습니다. 다른 방법으로 배열을 정적으로 표시하여 배열을 정적 저장소에 배치하거나 동적 메모리를 사용합니다.

태그가있는 C++ ... 사용하기 쉽고 동적 메모리를 사용하는 std::vector을 사용하십시오.

#include <vector> 
//... 
//... 
long long i,j,n; 
std::vector<bool> prime(100000000+1, true); 
prime[1]=prime[0]=false; 
for(i=2;i<=100000000;i++){ 
    if(prime[i]==false){ 
     continue; 
    } 
    for(j=i*2;j<=100000000;j+=i){ 
     prime[j]=false; 
    } 
} 

std::vector<bool> 여기에 표준 : : 벡터는 기존의 배열보다 약 여덟 ¹ 배 적은 메모리를 가지고 것을 의미합니다 "비트 효율적인"표현을 사용합니다.

std::bitset은 비슷하지만 크기가 일정하므로 자동 메모리 공간을 차지하지 않도록 정적으로 표시해야합니다.

당신은 물어 보지 않았지만 Erastostenes Sieve는 많은 소수를 계산하는 가장 빠른 알고리즘이 아닙니다. Sieve of Atkin은 더 빠르며 더 적은 메모리를 사용합니다.

- 시스템에 8 비트 바이트가있는 경우.

Answer 2

프라임 배열의 크기는 100MB이며 스택에 큰 배열이 허용되지 않도록 선언합니다. 전역 범위에 배열을 배치하여 힙에 할당하거나 new (C++) 또는 malloc (C)을 사용하여 할당하십시오. 그 후에 기억을 잊어 버리는 것을 잊지 마십시오!

Answer 3

아니요, 크기가 단일 모노 체를 만드십시오. 대신 에라 토 스테 네스 (Seat of Eratosthenes)를 세분화하여 연속 세그먼트에서 체질을 수행하십시오. 첫 번째 세그먼트에서 세그먼트 내에있는 체질 프라임의 가장 작은 배수가 계산 된 다음 체질 소수의 배수가 정상적인 방법으로 복합 표시됩니다. 모든 체질 소수가 사용되었을 때, 세그먼트의 남은 표시되지 않은 숫자는 소수입니다. 그런 다음 다음 세그먼트의 경우 각 체질 소수의 가장 작은 배수는 이전 세그먼트에서 체를 종료 한 배수이므로 체질은 완료 될 때까지 계속됩니다.

20의 세그먼트에서 100에서 200으로 체질하는 예를 고려하십시오. 5 번째 체질 소수는 3, 5, 7, 11 및 13이다. 100 내지 120의 제 1 세그먼트에서, 비트 어레이는 10 슬롯을 가지며, 슬롯 0은 101에 대응하고, 슬롯 k은 100 + 2 * k * + 1 및 슬롯 9는 119에 해당합니다. 세그먼트에서 3의 최소 배수는 105이며 슬롯 2에 해당합니다. 슬롯 2 + 3 = 5 및 5 + 3 = 8도 3의 배수입니다. 5의 최소 배수는 슬롯 2에서 105이고 슬롯 2 + 5 = 7 또한 5의 배수입니다. 7의 최소 배수는 105입니다 슬롯 2에서, 슬롯 2 + 7 = 9에서도 7의 배수입니다.

기능 primes 인수 LO, 안녕과델타 소요; 보라 및 하이이 하이의 제곱근보다 커야합니다 보라 < 하이 및 보라으로도 있어야합니다. 세그먼트 크기는 두 번 델타입니다. 배열 ps 길이가 m 인 제수 소수는 안녕의 제곱근보다 작습니다. 짝수는 무시되므로 일반 시럽 오브 에라토스테네스에 의해 계산되므로 2가 제거됩니다. 배열 qs에는 해당 체질 소수 부분의 현재 세그먼트에서 가장 작은 배수 인 시브 비트 배열의 오프셋이 포함됩니다. 각 세그먼트 후 두 델타, 그래서 인덱스 체 bitarray의 I에 대응하는 수만큼 LO 발전 LO + 2 I + 1

function primes(lo, hi, delta) 
    sieve := makeArray(0..delta-1) 
    ps := tail(primes(sqrt(hi))) 
    m := length(ps) 
    qs := makeArray(0..m-1) 
    for i from 0 to m-1 
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i] 
    while lo < hi 
    for i from 0 to delta-1 
     sieve[i] := True 
    for i from 0 to m-1 
     for j from qs[i] to delta step ps[i] 
     sieve[j] := False 
     qs[i] := (qs[i] - delta) % ps[i] 
    for i from 0 to delta-1 
     t := lo + 2*i + 1 
     if sieve[i] and t < hi 
     output t 
    lo := lo + 2*delta 

입니다 위에 주어진 샘플을 primes(100, 200, 10)이라고합니다. 상기 주어진 예에서, qs은 초기에 [2,2,2,10,8]이며, 가장 작은 배수 105, 105, 105, 121 및 117에 대응하고, 제 2 세그먼트에 대해 [1,2,6, 0,11], 최소 배수 123, 125, 133, 121 및 143에 해당합니다.

의 값은입니다. 당신은 델타을 가능한 한 크게 만들어서 속도를 위해 캐시 메모리에 맞춰야합니다. bitarray에 대한 언어 라이브러리를 사용하면 각 체 위치별로 한 비트 씩만 사용할 수 있습니다.

function primes(n) 
    sieve := makeArray(2..n, True) 
    for p from 2 to n step 1 
    if sieve(p) 
     output p 
     for i from p * p to n step p 
      sieve[i] := False 

당신은 더 알고리즘이 my blog에서 소수를 포함 볼 수 있습니다 : 당신이 체질 소수를 계산하는 데 에라 토 스테 네스의 간단한 체를해야하는 경우, 이것은 내가 가장 좋아하는 것입니다.