Eratosthenese sõel Python & C++

Mis on Eratosthenese sõel?

Eratosthenese sõel on lihtsaim algarvude sõel. See on algarvude algoritm, mida kasutatakse iga algarvu leidmiseks antud piirides. On olemas mitu algsõela, sealhulgas Eratosthenese sõel, Atkini sõel ja Sundarami sõel.

Sõna "sõel„viitab aineid filtreerivale tööriistale. Samas vaimus on ka sõela algoritm Python ja teised keeled viitavad meetodile, mis filtreerib täisarvude loendist välja algarvud.

See algoritm filtreerib algarvud iteratiivse lähenemisviisi abil. Filtreerimisprotsess algab väikseimast algarvust. Algarv on naturaalarv, mis on suurem kui 1 ja millel on ainult kaks jagajat, nimelt 1 ja arv ise. Numbers mis ei ole algarvud, nimetatakse liitarvudeks.

Miks kasutada Eratosthenese sõela?

Eratosthenese sõela meetodis valitakse esmalt väike algarv ja kõik selle kordsed filtreeritakse välja. Protsess toimib tsüklina antud vahemikus, genereerides tõhusalt kõik algarvud kuni n-ni ilma iga kandidaadi proovijagamist tegemata.

See muudab sõela kiiremaks kui algarvude kontrollimine ükshaaval. Seda kasutatakse laialdaselt arvuteoorias, krüptograafias, räsimises ja võistlusprogrammeerimises, kus tuleb kiiresti genereerida palju algarve.

Näiteks:

Võtame numbrite vahemiku 2 kuni 10.

Pärast Eratosthenese sõela rakendamist saadakse algarvude 2, 3, 5 ja 7 loend.

Eratosthenese algoritmi sõel

Siin on Eratosthenese sõela algoritm:

Step 1) Koostage arvude loend alates 2-st kuni antud vahemiku n-ni. Alustame arvust 2, sest see on väikseim ja esimene algarv.

Step 2) Vali loendist väikseim arv x (algselt on x võrdne 2-ga), käi loend läbi ja filtreeri vastavad liitarvud, märkides ära kõik valitud arvu kordsed.

Step 3) Seejärel valige loendist järgmine algarv või väikseim märgistamata arv ja korrake sammu 2.

Step 4) Korda eelmist sammu, kuni x väärtus on väiksem või võrdne n ruutjuurega (x<=).

Märge: Matemaatiline arutluskäik on üsna lihtne. Arvuvahemikku n saab faktoriseerida järgmiselt:

n = a * b

Jällegi n = *

= (tegur väiksem kui ) * (tegur suurem kui )

Nii et vähemalt üks neist peamised tegurid või mõlemad peavad olema <= Seega, liikudes ülespoole piisab.

Step 5) Pärast neid nelja sammu on ülejäänud märgistamata arvud kõik algarvud selles antud vahemikus n.

Töötatud näide

Näide:

Võtame näite ja vaatame, kuidas see toimib.

Selle näite jaoks leiame algarvude loendi 2-st 25-ni. Seega n = 25.

Step 1) Esimeses etapis võtame numbrite loendi vahemikus 2 kuni 25, kuna valisime n = 25.

Step 2) Seejärel valime loendist väikseima arvu x. Algselt x = 2, kuna see on väikseim algarv. Seejärel käime loendi läbi ja märgime arvu 2 kordsed.

Antud n väärtuse korral on arvu 2 kordsed: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Märge: Sinine värv tähistab valitud arvu ja roosa värv elimineeritud kordseid.

Step 3) Seejärel valime järgmise väikseima tähistamata arvu, milleks on 3, ja kordame viimast sammu, märkides 3 kordsed.

Step 4) Kordame 3. sammu samamoodi, kuni x = või 5.

Step 5) Ülejäänud märgistamata arvud on algarvud 2-st kuni 25-ni.

pseudo-Code

Järgnev pseudokood jäädvustab Eratosthenese sõela põhistruktuuri enne selle tegelikuks koodiks tõlkimist.

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Eratosthenese sõel C/C++ Code Näide

Allpool on täielik C++ Eratosthenese sõela rakendamine, mis prindib kõik algarvud kuni valitud ülempiirini.

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Väljund:

2 3 5 7 11 13 17 19 23

Eratosthenese sõel Python Programmi näide

Järgmised Python Programm rakendab sama algoritmi, kasutades tõeväärtusloendit ja while-tsüklit.

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Väljund:

2
3
5
7
11
13
17
19
23

Segmenteeritud sõel

Oleme näinud, et Eratosthenese sõel läbib tsükli kogu arvuvahemiku. Seega vajab see arvude salvestamiseks O(n) mäluruumi. Olukord muutub keerulisemaks, kui püüame leida algarve tohutus vahemikus, sest nii suure mäluploki eraldamine suurema n arvu jaoks pole teostatav.

Algoritmi saab optimeerida, lisades mõned uued funktsioonid. Idee on jagada arvuvahemik väiksemateks segmentideks ja arvutada nendes segmentides ükshaaval algarvud. See on tõhus viis ruumi keerukuse vähendamiseks. Seda meetodit nimetatakse a segmenteeritud sõel.

Optimeerimist saab saavutada järgmisel viisil:

1. Kasutage lihtsat sõela, et leida algarvud vahemikus 2 kuni ja salvestage need massiivi.
2. Jagage vahemik [0…n-1] maksimaalselt mitmeks segmendiks .
3. Iga lõigu puhul itereerige see läbi ja märkige 1. etapis leitud algarvude kordsed. See samm nõuab O() maksimaalselt.

Tavaline sõel nõuab O (n) lisamäluruumi, segmenteeritud sõel aga O (), mis on suure n korral oluline edasiminek. Meetodil on ka varjukülg, sest see ei paranda ajalist keerukust.

Keerukuse analüüs

Nii ruumilise kui ka ajalise keerukuse mõistmine aitab teil antud probleemi suuruse jaoks valida tavalise ja segmenteeritud sõela vahel.

Ruumi keerukus:

Eratosthenese lihtsa sõela algoritmi jaoks on vaja O(n) mälumahtu. Segmenteeritud sõela jaoks on vaja O() abiruum.

Aja keerukus:

Eratosthenese sõela algoritmi ajaline keerukus on O(n*log(log(n))). Selle keerukuse põhjuseid käsitletakse allpool.

Antud arvu n korral on liitarvu (st mittealgarvu) märkimiseks kuluv aeg konstantne. Seega tsükli korduste arv on võrdne:

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Algarvude summa harmoonilise progressiooni saab tuletada kujul log(log(n)):

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Seega on aja keerukus järgmine:

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Seega ajaline keerukus on O(n * log(log(n))).

Järgmisena saate teada, Pascali kolmnurk.

KKK