Tietorakenteet ja algoritmit syksy 2020

Algoritmin toteutus (osa 2)

Tehokkaampi tapa etsiä alkulukuja on Eratostheneen seula. Ideana on luoda taulukko, jossa arvo 0 tarkoittaa, että luku on alkuluku, ja arvo 1 tarkoittaa, että luku ei ole alkuluku.

Seuraava toteutus perustuu taulukkoon a, jossa on paikka jokaiselle luvulle väliltä 2–n. Algoritmin alussa taulukon jokainen arvo on 0, ja algoritmi merkitsee arvon 1 luvuille, jotka eivät ole alkulukuja. Sisemmässä silmukassa step i tarkoittaa, että muuttujan arvo kasvaa i:llä joka kierroksella.

count = 0
for i = 2 to n
    if a[i] == 0:
        count++
        for j = 2*i to n step i
            a[j] = 1
print(count)

Esimerkiksi kun n = 5, algoritmin tulisi antaa tulos 3, ja kun n = 100, algoritmin tulisi antaa tulos 25.

Toteuta algoritmi pseudokoodin perusteella Javalla tai Pythonilla ja vastaa sitten seuraaviin kysymyksiin:

Algoritmin testaus

Kun n = 1000, algoritmi antaa tuloksen ja aikaa kuluu sekuntia.

Kun n = 10000, algoritmi antaa tuloksen ja aikaa kuluu sekuntia.

Kun n = 100000, algoritmi antaa tuloksen ja aikaa kuluu sekuntia.

Algoritmin toteutus

Kirjoita tähän toteuttamasi algoritmin koodi:

The deadline for this task has passed but you can still check your answers

Return to task list