Zeef van Eratosthenes

Ik heb de zeef van Eratosthenes gelezen tijdens het oplossen van een vraag over Project Euler . Ik weet zeker dat jullie weten op welke vraag ik het heb. Dus hier is het ding. Mijn code slaagt er in om alle prime-lenzen minder dan 1 miljoen correct weer te geven. Nochtans wanneer ik de zelfde implementatie voor 2 miljoen probeer, krijg ik een segmentatiefout ... Ik heb een idee waarom de fout aanstaande is, maar ik weet niet hoe ik deze moet corrigeren ... Hier is de code voor prime-lenzen onder de 1 miljoen.

#include
int main(void)
{
   int i,k=2;
   int j;
   int n=1000000;
   int prime[2000000]={};
   for(i=0;in)
                  break;    
            }
         }
      }
   }
   for(i=0;i
3
Dit ziet er uit als een matrix die mogelijk buiten de grenzen valt: prime [j * prime [i]] = 0 .
toegevoegd de auteur Jon, de bron
Heeft u ervoor gekozen om int n = 1000000; in int n = 2000000; te wijzigen?
toegevoegd de auteur Dave, de bron
Als hij een grote reeks gaat indexeren, kan hij net zo goed size_t gebruiken
toegevoegd de auteur Dave, de bron
Van kanttekening, zou u waarschijnlijk een ander gegevenstype moeten gebruiken dan int . Er kan niet gegarandeerd worden dat Int een andere grootte heeft dan 16 bit. Als stijlnummer zou ik long aanbevelen voor nummers boven 32k.
toegevoegd de auteur logancautrell, de bron

1 antwoord

U wijst een enorme reeks stack toe:

int prime[2000000]={};

Vier bytes keer twee miljoen is acht megabytes, wat vaak de maximale stackgrootte is. Het toewijzen van meer dan dat resulteert in een segmentatiefout.

U moet de array in de heap toewijzen, in plaats daarvan:

int *prime;
prime = malloc(2000000 * sizeof(int));
if(!prime) {
    /* not enough memory */
}
/* ... use prime ... */
free(prime);
9
toegevoegd
4 * 2 * 10 ^ 6 = 7.6 * 2 ^ 20 = 7.6MB
toegevoegd de auteur Dave, de bron
Bedankt! ... Het werkt nu
toegevoegd de auteur Ole Gooner, de bron