Eratosthenes algoritmus szitája: Python, C++ Példa

Az Eratosthenes-szita a legegyszerűbb prímszám-szita. Ez egy prímszám-algoritmus, amely egy adott határon belüli összes prímszámot keres. Számos prímszám szita létezik. Például - Eratosthenes szita, Atkin szita, Sundaram szita stb.

A szó "szita” olyan edényt jelent, amely anyagokat szűr. Így a szita algoritmus be Python és más nyelvek a prímszámok kiszűrésére szolgáló algoritmusra utal.

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

Az Eratoszthenész módszer szitájában először egy kis prímszámot választanak ki, és ennek minden többszöröse kiszűrődik. A folyamat egy hurkon fut egy adott tartományban.

Például:

Vegyük a 2-től 10-ig terjedő számtartományt.

Az Eratoszthenész szita alkalmazása után elkészíti a 2, 3, 5, 7 prímszámok listáját.

Eratoszthenész algoritmus szitája

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

Step 1) Készítsen számlistát 2-től a megadott n tartományig. 2-vel kezdjük, mivel ez a legkisebb és első prímszám.

Step 2) Válassza ki a listából a legkisebb számot, az x-et (kezdetben x egyenlő 2-vel), menjen végig a listán, és szűrje ki a megfelelő összetett számokat a kiválasztott számok 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ételje meg 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 érvelés meglehetősen egyszerű. Az n számtartomány a következőképpen faktorizálható:

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. Így áthaladva a elég lesz.

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

Példa:

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

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

Step 1) Az első lépésben felvesszük a 2-től 25-ig terjedő számok listáját, mivel n=25-öt választottunk.

Step 2) Ezután kiválasztjuk a listából a legkisebb számot, 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ösét.

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

Jegyzet: A kék szín a kiválasztott számot jelöli, a rózsaszín pedig a kizárt többszöröseket

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) Ugyanígy ismételjük a 3. lépést x=-ig vagy 5.

Step 5) A fennmaradó nem jelölt számok a 2 és 25 közötti prímszámok.

Pszeudo-kód

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++ kód Példa

#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

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 szükséges ahhoz, hogy egy ciklust végigfusson a teljes számtartományon. Így a számok tárolásához O(n) memóriaterületre van szüksége. A helyzet bonyolulttá válik, ha hatalmas tartományban próbálunk prímeket találni. Nem lehetséges ekkora memóriaterületet lefoglalni egy nagyobb n számára.

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 szegmensnél ismételje meg a szakaszt, és jelölje meg az 1. lépésben talált prímszámok többszörösét. Ehhez a lépéshez O() max.

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 nagy előrelépés egy nagy n. A módszernek van egy hátránya is, mert nem javítja az időbonyolítást.

Komplexitás elemzése

Tér összetettsége:

Az eratosthenes algoritmus egyszerű szitája O(n) memóriaterületet igényel. A szegmentált szita pedig megkívánja
O() segédtér.

Idő összetettsége:

Az eratosthenes algoritmus szabályos szitájának időbonyolultsága O(n*log(log(n))). Ennek a bonyolultságnak az okait az alábbiakban tárgyaljuk.

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

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

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

A prímek összegének harmonikus progressziója log(log(n)-ként levonható).

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

Tehát az idő bonyolultsága

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 Pascal háromszöge

Összegzésként

• Az Eratoszthenész szita kiszűri a prímszámokat egy adott felső határon.
• Egy prímszám szűrése a legkisebb prímszámtól, a „2”-től kezdődik. Ez iteratív módon történik.
• Az iteráció n négyzetgyökéig történik, ahol n a megadott számtartomány.
• Ezen iterációk után a fennmaradó számok a prímszámok.