Eratosthenes-algoritmin seula: Python, C++ esimerkki

Eratosthenesin seula on yksinkertaisin alkulukuseula. Se on alkulukualgoritmi, joka etsii kaikki alkuluvut tietyssä rajassa. Alkulukuseuloja on useita. Esimerkiksi - Eratosthenesin seula, Atkinin seula, Sundaramin seula jne.

Sana "seula” tarkoittaa aineita suodattavaa astiaa. Siten seula-algoritmi sisään Python ja muut kielet viittaavat algoritmiin alkulukujen suodattamiseksi.

Tämä algoritmi suodattaa alkuluvun pois iteratiivisessa lähestymistavassa. Suodatusprosessi alkaa pienimmällä alkuluvulla. Alkuluku on luonnollinen luku, joka on suurempi kuin 1 ja jolla on vain kaksi jakajaa, nimittäin 1 ja itse luku. Lukuja, jotka eivät ole alkulukuja, kutsutaan yhdistelmäluvuiksi.

Eratosthenes-menetelmän seulassa valitaan ensin pieni alkuluku, jonka kaikki kerrannaiset suodatetaan pois. Prosessi suoritetaan silmukassa tietyllä alueella.

Esimerkiksi:

Otetaan lukualue välillä 2-10.

Kun Eratosthenesin seula on käytetty, se tuottaa luettelon alkuluvuista 2, 3, 5, 7

Eratosthenesin algoritmi

Tässä on Eratosthenesin seulan algoritmi:

Vaihe 1) Luo luettelo numeroista 2:sta annettuun alueeseen n. Aloitamme 2:sta, koska se on pienin ja ensimmäinen alkuluku.

Vaihe 2) Valitse luettelon pienin luku, x (alkuvaiheessa x on 2), selaa luetteloa ja suodata vastaavat yhdistelmäluvut merkitsemällä kaikki valittujen lukujen kerrannaiset.

Vaihe 3) Valitse sitten luettelosta seuraava alkuluku tai pienin merkitsemätön luku ja toista vaihe 2.

Vaihe 4) Toista edellinen vaihe, kunnes x:n arvon tulee olla pienempi tai yhtä suuri kuin n:n neliöjuuri (x<=).

Huomautus: Matemaattinen päättely on melko yksinkertainen. Numeroalue n voidaan kertoa seuraavasti:

n=a*b

Jälleen n =*

= (kerroin pienempi kuin ) * (kerroin suurempi kuin )

Joten ainakin yksi niistä päätekijät tai molempien on oltava <=. Näin ollen matkalla riittää.

Vaihe 5) Näiden neljän vaiheen jälkeen jäljellä olevat merkitsemättömät luvut olisivat kaikki alkuluvut kyseisellä alueella n.

Esimerkiksi:

Otetaan esimerkki ja katsotaan kuinka se toimii.

Tässä esimerkissä löydämme luettelon alkuluvuista 2-25. Joten n=25.

Vaihe 1) Ensimmäisessä vaiheessa otamme luettelon numeroista 2-25, kun valitsimme n = 25.

Vaihe 2) Sitten valitsemme luettelon pienimmän luvun, x. Aluksi x=2, koska se on pienin alkuluku. Sitten kuljemme luettelon läpi ja merkitsemme 2:n kerrannaiset.

2:n kerrannaiset annetulle n:n arvolle ovat: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Huomautus: Sininen väri tarkoittaa valittua numeroa, ja vaaleanpunainen väri tarkoittaa eliminoituja kerrannaisia

Vaihe 3) Sitten valitaan seuraavaksi pienin merkitsemätön luku, joka on 3, ja toistetaan viimeinen vaihe merkitsemällä 3:n kerrannaiset.

Vaihe 4) Toistamme vaihetta 3 samalla tavalla, kunnes x= tai 5.

Vaihe 5) Loput merkitsemättömät luvut olisivat alkulukuja 2-25.

Pseudokoodi

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 C/C++ koodi esimerkki

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

lähtö:

2 3 5 7 11 13 17 19 23

Eratosthenesin seula Python Ohjelmaesimerkki

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)

lähtö:

2
3
5
7
11
13
17
19
23

Segmentoitu seula

Olemme nähneet, että Eratosthenesin seulaa vaaditaan ajamaan silmukka koko lukualueen läpi. Siten se tarvitsee O(n) muistitilaa numeroiden tallentamiseen. Tilanne muuttuu monimutkaiseksi, kun yritämme löytää alkulukuja valtavalta alueelta. Ei ole mahdollista varata niin suurta muistitilaa isommalle n:lle.

Algoritmi voidaan optimoida ottamalla käyttöön joitain uusia ominaisuuksia. Ajatuksena on jakaa lukualue pienempiin segmentteihin ja laskea näiden segmenttien alkuluvut yksitellen. Tämä on tehokas tapa vähentää tilan monimutkaisuutta. Tätä menetelmää kutsutaan a segmentoitu seula.

Optimointi voidaan tehdä seuraavalla tavalla:

1. Käytä yksinkertaista seulaa löytääksesi alkuluvut 2:sta ja tallenna ne joukkoon.
2. Jaa alue [0…n-1] enintään useisiin segmentteihin
3. Iteroi jokaiselle segmentille segmentti ja merkitse vaiheessa 1 löydetty alkulukujen kerrannainen. Tämä vaihe vaatii O() max.

Tavallinen seula vaatii O(n) apumuistitilaa, kun taas segmentoitu seula vaatii O(n), mikä on suuri parannus suurelle n. Menetelmällä on myös haittapuolensa, koska se ei paranna ajan monimutkaisuutta.

Monimutkaisuusanalyysi

Avaruuden monimutkaisuus:

Eratosthenes-algoritmin yksinkertainen seula vaatii O(n) muistitilaa. Ja segmentoitu seula vaatii
O() aputilaa.

Ajan monimutkaisuus:

Eratosthenes-algoritmin säännöllisen seulan aikamonimutkaisuus on O(n*log(log(n))). Tämän monimutkaisuuden syitä käsitellään alla.

Tietylle luvulle n yhdistelmäluvun (eli ei-alkulukujen) merkitsemiseen tarvittava aika on vakio. Joten, kuinka monta kertaa silmukka suoritetaan, on yhtä suuri kuin -

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

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

Alkulukujen summan harmoninen eteneminen voidaan vähentää muodossa log(log(n)).

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

Joten aika monimutkaisuus tulee olemaan

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

= n * log(log(n))

Siten aikakompleksisuus O(n * log(log(n)))

Seuraavaksi opit aiheesta Pascalin kolmio

Yhteenveto

• Eratosthenesin seula suodattaa pois alkuluvut tietyssä ylärajassa.
• Alkuluvun suodatus alkaa pienimmästä alkuluvusta "2". Tämä tehdään iteratiivisesti.
• Iterointi suoritetaan n:n neliöjuureen asti, missä n on annettu lukualue.
• Näiden iteraatioiden jälkeen jäljelle jäävät luvut ovat alkulukuja.