Praštevila
Rešitve vseh nalog spravi v razred
Prastevilo in oddaj le eno
datoteko Prastevilo.java. Nekatere naloge imajo še dodatna
navodila, kako jih učinkovito rešimo. Za dodatno slavo in čast
upoštevaj navodila in napiši učinkovite rešitve.
Naloga 1
Sestavi metodo
prastevilo, ki sprejme celo število n
in vrne true, če je n praštevilo, sicer pa false.
Dodatno navodilo:
metoda naj preveri, ali je
n deljiv z 2, potem pa ali je
deljiv z lihimi števili 3, 5, 7, itn. Preveriti je treba le za taka
liha števila, katerih kvadrat ne presega n.
Naloga 2
Sestavi metodo
prastevila, ki sprejme pozitivno celo število
n in vrne tabelo prvih n praštevil.
Dodatno navodilo: Lažja rešitev uporabi rešitev prve naloge.
Boljša rešitev pa poišče naslednje praštevilo tako, da preverja
deljivost samo s tistimi praštevili, ki so že v tabeli. Na primer, če
smo že našli praštevila 2, 3, 5 in 7, potem pri iskanju naslednjega
praštevila preverjamo deljivost z 2, 3, 5 in 7. Tako 8 odpade, ker je
deljivo z 2, 9 odpade zaradi deljivosti s 3, 10 je deljivo z 2, 11 pa
ni deljivo z nobenim od 2, 3 (naprej ni treba preverjati, ker je 5 * 5
> 11), zato je praštevilo, ki ga dodamo v tabelo.
Naloga 3
Sestavi metodo, ki na zaslon izpiše razcep danega
pozitivnega celega števila glede na dano tabelo praštevil. Na
primer, če je
Se pravi, število delimo s prafaktorji iz tabele
n = 1540 in tabela praševil p
= {2, 3, 5}, metoda izpiše
1540 = 2 * 2 * 5 * 77 |
p, dokler to
gre. Zadnji faktor 77 ni razcepljen na 7 * 11, ker se v tabeli
p praštevilo 7 ali 11 ne pojavi.
Predpostaviti smeš, da so praštevila v tabeli p podana v
naraščajočem vrstnem redu.
Še en primer: če je
n = 40 in p = {2, 3, 5, 7, 11},
metoda izpiše
40 = 2 * 2 * 2 * 5 * 1 |