Eratoszthenész szitája Python & C++

Mi az Eratoszthenész szitája?

Az Eratoszthenész-szita a legegyszerűbb prímszám-szita. Ez egy prímszám-algoritmus, amelyet egy adott határon belüli összes prímszám megtalálására használnak. Több prímszita létezik, többek között az Eratoszthenész-szita, az Atkin-szita és a Szundaram-szita.

A szó "szita„egy olyan eszközre utal, amely anyagokat szűr. Ugyanebben a szellemben a szűrőalgoritmus is Python és más nyelveken egy olyan módszerre utal, amely kiszűri a prímszámokat egy egész számok listájából.

Ez az algoritmus iteratív megközelítéssel szűri a prímszámokat. A szűrési folyamat a legkisebb prímszámmal kezdődik. A prímszám egy 1-nél nagyobb természetes szám, amelynek csak két osztója van, nevezetesen 1 és maga a szám. Numbers Azokat a számokat, amelyek nem prímszámok, összetett számoknak nevezzük.

Miért használjuk Eratoszthenész szitáját?

Az Eratoszthenész-szűrő módszerében először egy kis prímszámot választanak ki, és annak összes többszörösét kiszűrik. A folyamat egy adott tartományon belül ciklusban fut, n-ig minden prímszámot hatékonyan előállítva anélkül, hogy minden jelöltön próbaosztást kellene végezni.

Ezáltal a szita gyorsabb, mint ha egyszerre csak egy számot ellenőriznénk a prímszámok számának ellenőrzésével. Széles körben használják a számelméletben, a kriptográfiában, a hashelésben és a versenyprogramozásban, ahol sok prímszámot kell gyorsan generálni.

Például:

Vegyük a számokat 2-től 10-ig.

Az Eratoszthenész-szita alkalmazása után a 2, 3, 5 és 7 prímszámok listáját fogja eredményezni.

Eratoszthenész algoritmus szitája

Íme az Eratoszthenész szitájának algoritmusa:

Step 1) Készíts egy számlistát 2-től az adott n tartományig. Kezdjük 2-vel, mert ez a legkisebb és egyben az első prímszám.

Step 2) Válassza ki a lista legkisebb számát, x-et (kezdetben x egyenlő 2-vel), menjen végig a listán, és szűrje a megfelelő összetett számokat a kiválasztott szám összes többszörösének megjelölésével.

Step 3) Ezután válassza ki a következő prímszámot vagy a legkisebb jelöletlen számot a listán, és ismételje meg a 2. lépést.

Step 4) Ismételd az előző lépést, amíg x értéke kisebb vagy egyenlő nem lesz n négyzetgyökével (x<=).

Jegyzet: A matematikai gondolkodás meglehetősen egyszerű. Az n számtartomány a következőképpen szorzattá alakítható:

n = a * b

Ismét n = *

= (tényező kisebb, mint ) * (tényező nagyobb, mint )

Tehát legalább az egyik elsődleges tényezők vagy mindkettőnek <=-nak kell lennie Ezért, felmászva a elég lesz.

Step 5) E négy lépés után a fennmaradó jelöletlen számok az adott n tartomány összes prímszámai lesznek.

Kidolgozott példa

Példa:

Vegyünk egy példát, és nézzük meg, hogyan működik.

Ebben a példában a 2-től 25-ig terjedő prímszámok listáját fogjuk keresni. Tehát n = 25.

Step 1) Az első lépésben 2-től 25-ig fogunk listázni számokat, mivel n = 25-öt választottunk.

Step 2) Ezután kiválasztjuk a lista legkisebb számát, az x-et. Kezdetben x = 2, mivel ez a legkisebb prímszám. Ezután végigmegyünk a listán, és megjelöljük a 2 többszöröseit.

Az adott n értékhez tartozó 2 többszörösei: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Jegyzet: A kék szín a kiválasztott számot, a rózsaszín pedig az eliminált többszörösöket jelöli.

Step 3) Ezután kiválasztjuk a következő legkisebb jelöletlen számot, ami 3, és megismételjük az utolsó lépést a 3 többszöröseinek megjelölésével.

Step 4) A 3. lépést ugyanígy ismételjük, amíg x = vagy 5.

Step 5) A fennmaradó jelöletlen számok a 2-től 25-ig terjedő prímszámok.

Ál-Code

A következő pszeudokód az Eratoszthenész-szűrő alapvető szerkezetét ragadja meg, mielőtt tényleges kóddá alakítanánk.

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

Eratosthenes szita C/C++ Code Példa

Az alábbiakban egy teljes C++ Az Eratoszthenész-szűrő implementációja, amely minden prímszámot kinyomtat egy kiválasztott felső határig.

#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;
}

output:

2 3 5 7 11 13 17 19 23

Eratoszthenész szita Python Program példa

A következő Python A program ugyanazt az algoritmust valósítja meg egy logikai lista és egy while ciklus használatával.

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)

output:

2
3
5
7
11
13
17
19
23

Szegmentált szita

Láttuk, hogy Eratoszthenész szitája egy ciklust futtat a teljes számtartományon keresztül. Ezért O(n) memóriaterületre van szüksége a számok tárolásához. A helyzet bonyolulttá válik, amikor egy hatalmas számtartományban próbálunk prímszámokat találni, mivel nem lehetséges ilyen nagy memóriablokkot lefoglalni egy nagyobb n számhoz.

Az algoritmus optimalizálható néhány új funkció bevezetésével. Az ötlet az, hogy a számtartományt kisebb szegmensekre osztjuk, és ezekben a szegmensekben egyenként számítsuk ki a prímszámokat. Ez egy hatékony módja a tér összetettségének csökkentésének. Ezt a módszert a tagolt szita.

Az optimalizálás a következő módon valósítható meg:

1. Egy egyszerű szitával keresse meg a 2-től kezdődő prímszámokat és tárolja őket egy tömbben.
2. Ossza fel a [0…n-1] tartományt legfeljebb több méretű szegmensre .
3. Minden szakasz esetében iteráljuk végig a szakaszt, és jelöljük meg az 1. lépésben talált prímszámok többszöröseit. Ehhez a lépéshez O() maximum.

A normál szitához O(n) kiegészítő memóriaterületre van szükség, míg a szegmentált szitához O(), ami jelentős javulás nagy n esetén. A módszernek van egy hátránya is, mivel nem javítja az időbonyolultságot.

Komplexitás elemzése

A térbeli és időbeli komplexitás megértése segít választani a hagyományos és a szegmentált szita között egy adott problémaméret esetén.

Tér összetettsége:

Az egyszerű Eratoszthenész-szita algoritmus O(n) memóriaterületet igényel. A szegmentált szita O() segédtér.

Idő összetettsége:

Egy szabályos Eratoszthenész-szita algoritmus időbonyolultsága O(n*log(log(n))). Az alábbiakban ezt a bonyolultságot tárgyaljuk.

Egy adott n szám esetén az összetett szám (azaz egy nem prímszám) megjelöléséhez szükséges idő állandó. Tehát a ciklus lefutásainak száma egyenlő:

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

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

A prímszámok összegének harmonikus sorozata a log(log(n)) képlettel levezethető:

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

Tehát az időbonyolultság a következő lesz:

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

= n * log(log(n))

Így az időbonyolultság O(n * log(log(n))).

Ezután megtudhatja, hogy Pascal háromszöge.

GYIK