Eratostheneen seula Python & C++

Mikä on Eratostheneen seula?

Eratostheneen seula on yksinkertaisin alkulukuseula. Se on alkulukualgoritmi, jota käytetään löytämään kaikki alkuluvut tietyn rajan sisällä. On olemassa useita alkulukuseuloja, mukaan lukien Eratostheneen seula, Atkinin seula ja Sundaramin seula.

Sana "seula” viittaa välineeseen, joka suodattaa aineita. Samassa hengessä seula-algoritmi Python ja muut kielet viittaa menetelmään, joka suodattaa alkuluvut kokonaislukuluettelosta.

Tämä algoritmi suodattaa alkulukuja iteratiivisella lähestymistavalla. Suodatusprosessi alkaa pienimmästä alkuluvusta. Alkuluku on luonnollinen luku, joka on suurempi kuin 1 ja jolla on vain kaksi jakajaa, nimittäin 1 ja itse luku. Numbers jotka eivät ole alkulukuja, kutsutaan yhdistettyiksi luvuiksi.

Miksi käyttää Eratostheneen seulaa?

Eratostheneen seulamenetelmässä valitaan ensin pieni alkuluku ja kaikki sen monikerrat suodatetaan pois. Prosessi toimii silmukassa tietyllä alueella ja tuottaa tehokkaasti kaikki alkuluvut n:ään asti ilman, että jokaiselle ehdokkaalle suoritetaan koejakolaskua.

Tämä tekee seulasta nopeamman kuin alkulukujen tarkistaminen yksitellen. Sitä käytetään laajalti lukuteoriassa, kryptografiassa, hajautuksessa ja kilpailuohjelmoinnissa, joissa on luotava nopeasti useita alkulukuja.

Esimerkiksi:

Otetaan lukuväli 2-10.

Eratostheneen seulan levittämisen jälkeen saadaan lista alkuluvuista 2, 3, 5 ja 7.

Eratosthenesin algoritmi

Tässä on Eratosthenesin seulan algoritmi:

Vaihe 1) Luo lista luvuista 2:sta annettuun väliin n. Aloitamme luvusta 2, koska se on pienin ja ensimmäinen alkuluku.

Vaihe 2) Valitse listalta pienin luku x (aluksi x on 2), käy lista läpi ja suodata vastaavat yhdistettyjä luvut merkitsemällä valitun luvun kaikki monikerrat.

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 arvo on pienempi tai yhtä suuri kuin n:n neliöjuuri (x<=).

Huomautus: Matemaattinen päättely on melko yksinkertaista. Lukuväli n voidaan jakaa tekijöihin seuraavasti:

n = a * b

Jälleen n = *

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

Joten ainakin yksi niistä päätekijät tai molempien on oltava <= Siksi ylitys kohti riittää.

Vaihe 5) Näiden neljän vaiheen jälkeen jäljellä olevat merkitsemättömät luvut ovat kaikki alkuluvut annetulla välillä n.

Toiminut esimerkki

Esimerkiksi:

Otetaan esimerkki ja katsotaan, miten se toimii.

Tässä esimerkissä etsimme alkulukujen luettelon 2:sta 25:een. Joten n = 25.

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

Vaihe 2) Sitten valitsemme listalta pienimmän luvun, x. Aluksi x = 2, koska se on pienin alkuluku. Sitten käymme listan läpi ja merkitsemme luvun 2 monikerrat.

Annetun n:n arvon 2 monikerrat ovat: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Huomautus: Sininen väri tarkoittaa valittua numeroa ja vaaleanpunainen väri eliminoituja monikertoja.

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 vaiheen 3 samalla tavalla, kunnes x = tai 5.

Vaihe 5) Loput merkitsemättömät luvut ovat alkuluvut 2:sta 25:een.

Pseudo-Code

Seuraava pseudokoodi kuvaa Eratostheneen seulan perusrakenteen ennen kuin käännämme sen varsinaiseksi koodiksi.

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++ Code esimerkki

Alla on täydellinen C++ Eratostheneen seulan toteutus, joka tulostaa kaikki alkuluvut valittuun ylärajaan asti.

#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

Seuraavat Python ohjelma toteuttaa saman algoritmin käyttämällä totuusarvoista listaa ja while-silmukkaa.

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ä Eratostheneen seula käy läpi koko lukuvälin. Siksi se tarvitsee O(n) muistitilaa lukujen tallentamiseen. Tilanne mutkistuu, kun yritämme löytää alkulukuja valtavalta väliltä, ​​koska ei ole mahdollista varata niin suurta muistilohkoa suuremmalle n luvulle.

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. Jokaiselle janalle iteroi jana läpi ja merkitse vaiheessa 1 löydettyjen alkulukujen monikerrat. Tämä vaihe vaatii O() enintään.

Tavallinen seula vaatii O(n) apumuistitilaa, kun taas segmentoitu seula vaatii O(n), mikä on huomattava parannus suurella n:llä. Menetelmällä on myös haittapuolensa, koska se ei paranna aikakompleksisuutta.

Monimutkaisuusanalyysi

Sekä tila- että aikakompleksisuuden ymmärtäminen auttaa sinua valitsemaan tavallisen seulan ja segmentoidun seulan välillä tietyn ongelman koon mukaan.

Avaruuden monimutkaisuus:

Yksinkertainen Eratostheneen seula-algoritmi vaatii O(n) muistitilaa. Segmentoitu seula vaatii O() aputilaa.

Ajan monimutkaisuus:

Eratostheneen seula-algoritmin aikavaativuus on O(n*log(log(n))). Tämän monimutkaisuuden taustalla olevia perusteluja käsitellään alla.

Annetulla luvulla n yhdistettyjen lukujen (eli alkuluvuista poikkeavien lukujen) merkitsemiseen kuluva aika on vakio. Joten silmukan suorituskertojen määrä on yhtä suuri kuin:

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

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

Alkulukujen summan harmoninen johdanto voidaan päätellä muodossa log(log(n)):

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

Joten aikakompleksisuus on:

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

= n * log(log(n))

Näin ollen aikakompleksisuus on O(n * log(log(n))).

Seuraavaksi opit mm. Pascalin kolmio.

UKK