C - Primzahlen von bestimmten BIG RANGE erhalten

Question

#include <stdio.h> 
#include <math.h> 
#define UPPER_LIMIT 2147483647 
void sieve(unsigned long int n, unsigned long int primes[]); 
main() 
{ 
    unsigned long int low, up, steps; 
    unsigned long int v[UPPER_LIMIT]; 
    sieve(UPPER_LIMIT, v); 
    scanf("%ld\n",&steps); 
    for (unsigned long int i=0;i<steps;i++){ 
     scanf("%ld %ld\n",&low,&up); 
     for(unsigned long int j=low; j<up; j++){ 
      if (v[j] == 1){ 
       printf("%ld\n",j); 
      } 
     } 
    } 
} 
void sieve(unsigned long int n, unsigned long int primes[]) 
{ 
    for (unsigned long int i=0;i<n;i++){ 
     primes[i]=1; 
    } 
    primes[0]=0,primes[1]=0; 

    for (unsigned long int i=2;i<sqrt(n);i++) { 
     for (unsigned long int j=i*i;j<n;j+=i){ 
      primes[j] = 0; 
     } 
    } 
} 

Ich versuche, das Problem zu lösen, Primzahlen aus einem bestimmten Bereich zu drucken. Zuerst erhalten wir scanf Anzahl der Fälle überprüft werden. Der Bereich wird durch die nächsten Zeilen von stdin angegeben, z. B. (1 10) der obere Wert kann maximal 2147483647 sein. Ich benutze Sieb aus Erastostens, um Primzahlen zu finden. Danach möchte ich printf Primzahlen in aufsteigender Reihenfolge. Leider bekomme ich einen Runtime Error, und ich nehme an, das liegt an dem sehr großen Array, das ich erstellen möchte. Ich brauche einen Rat zur möglichen Lösung des Problems.

Beispiel von stdin:

1 
1 10 

Beispiel stdout:

2 
3 
7 

Answer 1

erklärt Globally den Primzahlen-Array mit max Größe.
Sie können Vektor verwenden, um Primzahlen (C++ Container) zu speichern.
Und Array-Größe kann bestenfalls 10^7 bis 10^8, Sie nicht unsigned long int v[2147483647]; dieses große Array erklären können Auch Sie können das Problem nicht durch diesen Ansatz lösen :).

Answer 2

Sie versuchen, eine lokale Variable, die in den meisten Implementierungen auf dem Stack lebt, sehr groß zu erstellen. Bei 2G-Elementen vom Typ unsigned long werden Sie höchstwahrscheinlich auf 8 GB oder 16 GB schauen. Das ist viel zu groß für den Stapel.

Erstellen Sie diese Variable stattdessen als globale Variable. Auf diese Weise wird es nicht auf dem Stapel leben, sondern in (abhängig von der Implementierung) dem Datenabschnitt.

Da diesem Array nur die Werte 0 und 1 zugewiesen werden, ändern Sie den Typ des Arrays in char, so dass jedes Element nur 1 Byte verwendet. Das wird dir eine Menge Speicher ersparen.

Answer 3

Es ist sinnlos, ein unsigned long Array zu verwenden, um nur 0 oder 1 zu speichern.

Sie brauchen nur 2147483647/8 Bits, die alle Informationen zu speichern, die Sie benötigen, so sollten Sie eine Reihe von höchstens 2147483647/8 + 1 Bytes deklarieren:

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char primes[SIZE]; 

Oder noch besser, durch Heapzuordnung:

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char *primes = (unsigned char*)malloc(SIZE); 

Die Array-Initialisierung wird:

Der Zugriff auf einzelne Bits des Arrays kann mit den bitweisen Operatoren >>, << und & erfolgen. Dies umzusetzen ist eine Übung, da dies wie eine universitäre Übung aussieht.