Sil av eratosthenes med C ++

Et primtall er et naturlig (hel) tall som er større enn eller lik to, som bare kan deles av seg selv og 1. De første primtallene er: 2, 3, 5, 7, etc.

For nummer 5 er antallet primtall som er opp til og/eller inkludert 5:

2, 3, 5

For nummer 8 er antallet primtall som er opp til og/eller inkludert 8:

2, 3, 5, 7

For nummer 19 er antallet primtall som er opp til og/eller inkludert 19:

2, 3, 5, 7, 11, 13, 17, 19

For tallet 25 er antallet primtall som er opp til og/eller inkludert 25:

2, 3, 5, 7, 11, 13, 17, 19, 23

For tallet 36 er antall primtall som er opp til og/eller inkludert 36:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

For tallet 37 er antallet primtall som er opp til og/eller inkludert 37:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Disse listene er bare eksempler. Det er mange andre eksempellister med primtall nedenfor og/eller inkludert et gitt tall. Begynn forståelsen av silen til Eratosthenes ved å merke seg at primtallene under et mindre gitt tall er de samme som den første delen av primtallene under et gitt større tall.

Silen til Eratosthenes er en teknikk for å finne alle primtallene som er mindre enn eller lik et gitt tall som 36 eller 37 ovenfor. Dette tallet som 36 eller 37 får vanligvis variabelnavnet “N” i programmering. Silen til Eratosthenes regnes som en effektiv algoritme for å få listen over primtall.

Demonstrasjon for sil av eratosthenes

Spørsmålet er: Finn primtallene mindre enn eller lik 5, for eksempel på en effektiv måte. Den effektive måten her betyr å bruke så få operasjoner som mulig. Primtallene begynner fra 2. Alle tallene inkludert multiplene med små primtall fra 2 til 5 er:

2, 3, 4, 5

I dette området er et tall som ikke er et primtall et multiplum av et tidligere primtall. Et multiplum kan oppnås ved tillegg av samme primtall, om og om igjen. For eksempel er 2 + 2 4, pluss 2 igjen er 6. Og det foregår utover rekkevidden. Fire, som er et multiplum av 2, skal ikke være på listen fordi det ikke er et primtall. Ligningen 3 + 3 er 6, som allerede er utenfor rekkevidden. Og 6 eller et hvilket som helst nummer utover området skal ikke være på listen. Så resultatet er som følger:

2, 3, 5

Antallet det gjelder her er 5. Kvadratroten til 5 er 2.24. Heltallverdien for kvadratroten av 5 er 2. Multiplene med primtall under og opptil 2, som er heltallverdien for kvadratroten til 5, fjernes fra listen over alle tallene.

Tenk nå, nummer 8. Alle tallene inkludert multiplene med små primtall fra 2 til 8 er:

2, 3, 4, 5, 6, 7, 8

Ligningen 2 + 2 er 4. Fire går ut. Ligningen 4+2 er 6. Seks går ut. Ligningen 6 + 2 er 8. Åtte er ute. Neste primtall å vurdere er 3. Ligningen 3 + 3 er 6. Seks er allerede utelukket av kontinuerlig tillegg av 2. Ligningen 6 + 3 er 9; som er utenfor rekkevidde. Primtallene mellom 2 og 8, inkluderende, er:

2, 3, 5, 7

Antallet det gjelder her er 8. Kvadratroten av 8 er 2.83. Heltallverdien for kvadratroten av 8 er 2. Multiplene av primtall.

Et lignende problem er å liste opp primtallene fra 2 til 19, inkluderende. Alle tallene fra 2 til 19, inkluderende er:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

Ligningen 2 + 2 er 4; 4 er ute. Ligningen 4 + 2 er 6; 6 er ute. Ligningen 6 + 2 er 8; 8 er ute. Ligningen 8 + 2 er 10; 10 er ute. Ligningen 10 + 2 er 12; 12 er ute. Ligningen 12 + 2 er 14; 14 er ute. Ligningen 14 + 2 er 16; 16 er ute. Ligningen 16 + 2 er 18; 18 er ute. Ligningen 18 + 2 er 20, som er over området; 20 er ute.

Neste primtall å vurdere, og går oppover mot kvadratroten av 19, er 3. Ligningen 3 + 3 er 6; 6 er allerede utelukket som et multiplum av 2. Ligningen 6 + 3 er 9; 9 går ut. Ligningen 9 + 3 er 12; 12 er allerede utelukket som et multiplum av 2. Ligningen 12 + 3 er 15; 15 er ute. Ligningen 15 + 3 er 18; 18 er allerede utelukket som et multiplum av 2. Ligningen 18 + 3 er 21, som er over området. Resultatet er:

2, 3, 5, 7, 11, 13, 17, 19

Antallet det gjelder her er 19. Kvadratroten av 19 er 4.36. Heltallverdien for kvadratroten av 19 er 4. Multiplene med primtall under og opptil 4, som er heltallverdien for kvadratroten av 19 blir fjernet.

Primtallene nedenfor og opptil 4 er: 2 og 3. På grunn av 3 var det ikke noe poeng i å fjerne tallene 6, 12 og 18 som er multipler på 3, som allerede er fjernet som multipler på 2. Bare multiplene på 3 som ikke er multipler av 2, fjernes på grunn av 3. I praksis, etter å ha fjernet multiplene på 2, bør bare multiplene fra og over 3 x 3 = 9 fjernes uten å gjenta fjerning av 6. På grunn av 3 er tallene som skal fjernes 9, 12, 15 og 18; med 12 og 18 fjernet to ganger i teorien. Nummer 6 bør fjernes en gang og ikke to ganger.

La n være 25, et nytt nummer det gjelder. Alle tallene fra 2 til 25 er:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Ligningen 2 + 2 er 4; 4 går ut. Ligningen 4 + 2 er 6; 6 er ute. Ligningen 6 + 2 er 8; 8 er ute. Ligningen 8 + 2 er 10; 10 er ute. Ligningen 10 + 2 er 12; 12 er ute. Ligningen 12 + 2 er 14; 14 er ute. Ligningen 14 + 2 er 16; 16 er ute. Ligningen 16 + 2 er 18; 18 er ute. Ligningen 18 + 2 er 20; 20 er ute. Ligningen 20 + 2 er 22; 22 er ute. Ligningen 22 + 2 er 24; 24 er ute. Ligningen 24 + 2 er 26, som er over området.

Neste primtall å vurdere, og gå oppover mot kvadratroten av 25, er 3. Ligningen 3 + 3 er 6; 6 er allerede utelukket som et multiplum av 2. Ligningen 6 + 3 er 9; 9 går ut. Ligningen 9 + 3 er 12. Tolv er allerede utelukket som et multiplum av 2. Ligningen 12 + 3 er 15; 15 er ute. Ligningen 15 + 3 er 18; 18 er allerede utelukket som et multiplum av 2. Ligningen 18 + 3 er 21; 21 går ut. Ligningen 21 + 3 er 24; 24 er allerede utelukket som et multiplum av 2. Ligningen 24 + 3 er 27, som er over området.

Neste primtall å vurdere, gå oppover mot kvadratroten av 25 som er 5, er 5. Ligningen 5 + 5 er 10; 10 er allerede utelukket som et multiplum av 2. Ligningen 10 + 5 er 15; 15 er allerede utelukket som et multiplum av 3. Ligningen 15 + 5 er 20; 20 er allerede utelukket som et multiplum av 2. Ligningen 20 + 5 er 25; 25 går ut. Resultatet er:

2, 3, 5, 7, 11, 13, 17, 19, 23

Antallet det gjelder her er 25. Kvadratroten på 25 er 5. Heltallverdien for kvadratroten på 25 er 5. Multiplene med primtall under og opptil 5, som er heltallverdien for kvadratroten på 25, fjernes.

Primtallene nedenfor og opptil 5 er 2, 3 og 5. På grunn av 2 er tallene som antas å fjernes fra listen over alle tallene etter multipler: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 og 24. På grunn av 3 er tallene som antas å fjernes fra listen etter multipler: 6, 9, 12, 15, 18, 21 og 24. På grunn av 5 er tallene som antas å fjernes med multipler: 10, 15, 20 og 25.

Etter alle multipler er fjerningene som følger:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

Ved multipler fjernes 6 to ganger (i teorien) fjernes 10 to ganger (i teorien), 12 fjernes to ganger (i teorien) fjernes 15 to ganger (i teorien), 20 fjernes to ganger (i teori), og 24 fjernes to ganger (i teorien).

Imidlertid, hvis fjerningen på grunn av 3 begynner fra 3 x 3 = 9, fjernes 6 bare en gang. Hvis fjerningen på grunn av 5 begynner fra 5 x 5 = 25, blir fjerning av 10, 15 og 20 utført en gang hver. Fjerning av 12, 18 og 24 gjøres imidlertid fortsatt to ganger per antall. Fortsatt ville det være en viss fordel, ettersom fire gjentatte operasjoner for fjerning er utelatt (for 6, 10, 15 og 20). Dette forbedrer effektiviteten (tidskompleksitet). Med det vil fjerningene være:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

Tallene 6, 10, 15 og 20 har blitt fjernet en gang, i stedet for to ganger. Tallene, 12, 18 og 24 er hver fjernet to ganger. Per nå kan ingenting gjøres for å fjerne 12, 18 og 24 bare en gang.

Situasjonene for tallene 36 og 37, eller noe annet antall større enn 1, er på samme måte forklart.

Unngå redundans

Ved bare. Effektiviteten kan forbedres ved å fjerne multiplene med primtall, fra og med torget til primtallet (i²) opp til heltallverdien til √n som tidligere antydet. Dette utelater noe antall fjerningsoperasjoner. Så å redusere det totale antallet operasjoner. Sikt av Eratosthenes gjøres ved denne andre tilnærmingen.

Algoritme av silen til eratosthenes

Algoritmen begynner med å lage en nullbasert indeksert lengdevektor som er n+1. Hvert element i denne vektoren initialiseres til boolsk, sant, bortsett fra de første og andre elementene for indeks 0 og indeks 1 som initialiseres til falske. For denne vektoren tilsvarer indeksen 2 antallet (prime) 2; Indeksen 3 tilsvarer tallet (prime) 3; Indeksen 4 tilsvarer nummer 4; og så videre. Siden vektoren er null en basert indeks, må lengden være n+1 slik at den siste indeksen tilsvarer n.

Et indeksnummer for denne vektorlisten som må fjernes, fjernes ikke i seg selv: Verdien av indeksnummeret blir gjort usant for å indikere fjerning. Det vil si at elementet får den falske verdien. Så hvis et tall (indeks) må fjernes fra listen (vektoren) mer enn en gang, blir verdien for indeksen gjort falsk mer enn en gang.

På slutten blir indeksene for elementene i vektoren hvis verdier forble sanne lest opp som primtall.

Før da er multiplene av primindekser som begynner fra torget til primeindeksen (i²) opp til heltallverdien til √n er merket som falske.

C ++ koding

Programmet i C ++, bør begynne med følgende:

#inkludere
#inkludere
ved hjelp av navneområdet STD;

Silen til Eratosthenes -funksjonen er som følger:

vektor Sieve (int n)
vektor sil (n+1, sant);
sil [0] = falsk;
sil [1] = falsk;
int i = 2;
mens (jeg * jeg <= n)
if (sil [i] == true) // hvis jeg er primtall
int j = i * i;
mens (j <= n) //marking multiples with false
sil [j] = falsk;
j = j + i; // økning med flere


i = i + 1; // normal økning av ytre sløyfe, med 1

retursil;

Les kommentarene til koden. Navnet på funksjonen er sil (). Den returnerte vektoren, etter at alle multiplene er merket som falske, kalles også sil. En passende C ++ hovedfunksjon for denne koden er:

int main (int argc, char ** argv)

vektor VTR = Sieve (37);
for (int i = 0; iif (vtr [i] == true)
cout << i << ";
cout << endl;
retur 0;

Med denne koden er utgangen som følger:

2 3 5 7 11 13 17 19 23 29 31 37

Tidskompleksiteten for denne funksjonen er o (n log log n).

Konklusjon

Algoritmen begynner med å lage en nullbasert indeksert vektor av lengden n+1. Hvert element i denne vektoren initialiseres til boolsk, sant, bortsett fra de første og andre elementene for indeks 0 og indeks 1 som initialiseres til falske. For denne vektoren er hver indeks en rekke interesse. Siden vektoren er nullbasert indeksert, må lengden være n+1 slik at den siste indeksen er n.

Verdien av antallet som er indeksen blir gjort usant for å indikere fjerning. Det vil si at elementet får den falske verdien.

På slutten blir indeksene for elementene i vektoren hvis verdier forble sanne lest opp som primtall.

Før da er multiplene av primindekser som begynner fra torget til primindeksen opp til heltallverdien av √n, merket som falske.