Tietorakenteet ja algoritmit syksy 2020

Algoritmin toteutus (osa 1)

Positiivinen kokonaisluku on alkuluku, jos se on jaollinen vain 1:llä ja itsellään. Esimerkiksi luvut 3, 7 ja 19 ovat alkulukuja. Luku 10 puolestaan ei ole alkuluku, koska se on jaollinen 2:lla ja 5:llä.

Seuraava algoritmi laskee, montako alkulukua on välillä 2–n. Algoritmi tarkastaa jokaisesta luvusta i, onko se jaollinen jollain luvulla, joka on vähintään 2 ja enintään i–1. Jos tällainen jakaja löytyy, luku ei ole alkuluku, ja muuten luku on alkuluku.

count = 0
for i = 2 to n
    prime = true
    for j = 2 to i-1
        if i%j == 0
            prime = false
            break
    if prime
        count++
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