Python stazaCjelina 2 · Igra s brojevimaLekcija 11

Djeljivost i prosti brojevi

Koji brojevi dijele 12? Je li 97 prost broj? Uz petlju i ostatak dijeljenja program to brzo provjeri.

Pythonoko 45 minuta3 zadatka za evaluator

1Djelitelji broja

Broj d je djelitelj broja n ako dijeli n bez ostatka, to jest ako je n % d == 0. Sve djelitelje nađemo tako da redom isprobamo brojeve od 1 do n.

n = int(input())
for d in range(1, n + 1):
    if n % d == 0:
        print(d)
Ulaz
12
Ispis
1 2 3 4 6 12
Ključna ideja

Svaki broj je djeljiv s 1 i sa samim sobom. Zato petlja ide od 1 do n, to jest range(1, n + 1).

2Prosti brojevi

Broj je prost ako ima točno dva djelitelja: 1 i samog sebe. Prosti brojevi su 2, 3, 5, 7, 11, 13… Broj 1 nije prost, jer ima samo jedan djelitelj.

Prvi način: prebrojimo djelitelje. Ako ih je točno 2, broj je prost.

n = int(input())
djelitelja = 0
for d in range(1, n + 1):
    if n % d == 0:
        djelitelja += 1
if djelitelja == 2:
    print("prost")
else:
    print("nije prost")
Ulaz
13
Ispis
prost

3Zastavica

Drugi način: pretpostavimo da je broj prost, pa tražimo dokaz da nije. Ako neki broj između 2 i n − 1 dijeli n, pretpostavka je pala. Varijablu koja pamti „je li se nešto dogodilo“ zovemo zastavica.

d–
prost–
Klikni „Sljedeći korak“ i prati što se događa.
Ključna ideja

True i False možemo spremiti u varijablu i koristiti kao uvjet: if prost:

Pazi

Za n = 1 petlja se ne izvrši nijednom i zastavica ostane True, a 1 nije prost. Taj slučaj treba provjeriti posebno.

U praćenju se vidi da petlja nastavlja provjeravati 4, 5, 6, 7 i 8, iako već nakon 3 znamo da 9 nije prost. S break iz lekcije 8 petlja staje čim nađe djelitelj:

n = int(input())
prost = True
for d in range(2, n):
    if n % d == 0:
        prost = False
        break
print(prost)
Ulaz
9
Ispis
False

4Brže: do korijena

Djelitelji dolaze u parovima. Pogledaj broj 36:

ManjiVećiUmnožak
13636
21836
31236
4936
6636

U svakom paru manji djelitelj nije veći od 6, a 6 · 6 = 36. Zato je dovoljno isprobati brojeve d za koje je d * d <= n. Ako do tada nismo našli djelitelj, neće ga ni biti.

n = int(input())
prost = True
if n < 2:
    prost = False
d = 2
while d * d <= n:
    if n % d == 0:
        prost = False
    d += 1
if prost:
    print("prost")
else:
    print("nije prost")
Ključna ideja

Za broj oko milijarde, prvi način isproba milijardu brojeva, a ovaj samo oko 31 600. Evaluator ima vremensko ograničenje, pa je to razlika između točnog i prespororog rješenja.

5Najveći zajednički djelitelj

Najveći zajednički djelitelj (NZD) brojeva a i b najveći je broj koji dijeli oba. NZD brojeva 12 i 18 je 6.

a = int(input())
b = int(input())
nzd = 1
for d in range(1, a + 1):
    if a % d == 0 and b % d == 0:
        nzd = d
print(nzd)
Ulaz
12 18
Ispis
6
Stani i razmisli

Zašto u varijabli nzd na kraju ostane baš najveći zajednički djelitelj?

Pogledaj odgovor

Petlja ide od manjih prema većim brojevima. Svaki zajednički djelitelj prepiše prethodni, pa zadnji upisani je najveći.

6Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Je li 1 prost broj?

Pitanje

Zašto je dovoljno provjeravati djelitelje do korijena broja?

Pitanje

Koliko je NZD(12, 18)?

7Zadaci

Djelitelji

★☆☆ lagano

Ispiši sve djelitelje prirodnog broja N, od najmanjeg prema najvećem.

Ulaz
Jedan prirodni broj N.
Izlaz
Djelitelji broja N, svaki u svom retku.
Ograničenja
1 ≤ N ≤ 10 000
Ulaz
10
Izlaz
1 2 5 10
Riješi u evaluatoru

Pločice

★★☆ srednje

Pod je pravokutnik dimenzija A × B decimetara. Želimo ga popločiti jednakim kvadratnim pločicama, bez rezanja. Kolika je najveća moguća stranica pločice u decimetrima?

Ulaz
Jedan redak s dva broja A i B.
Izlaz
Najveća stranica kvadratne pločice.
Ograničenja
1 ≤ A, B ≤ 1000
Ulaz
12 18
Izlaz
6
Treba ti pomoć?

Stranica pločice mora dijeliti i A i B. Koji takav broj je najveći?

Riješi u evaluatoru

Prost broj

★★★ teže

Je li zadani broj prost?

Ulaz
Jedan prirodni broj N.
Izlaz
DA ako je N prost, inače NE.
Ograničenja
1 ≤ N ≤ 1 000 000 000
Ulaz
97
Izlaz
DA
Ulaz
91
Izlaz
NE
Treba ti pomoć?

N može biti i milijarda, pa rješenje koje isprobava sve brojeve do N neće stići u roku. Pogledaj dio 4.

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Kviz Infokup 2017 · županijsko · 6. r. OŠ
  2. Sfenički Infokup 2017 · školsko · 8. r. OŠ

8Što smo naučili

  • d je djelitelj od n ako je n % d == 0.
  • Prost broj ima točno dva djelitelja; 1 nije prost.
  • Zastavica je varijabla s True ili False koja pamti je li se nešto dogodilo.
  • Za provjeru prostosti dovoljno je ići dok je d * d <= n.
Najčešće greške

1 proglašen prostim · petlja od 0 (dijeljenje s nulom) · range(1, n) koji preskoči sam n · presporo rješenje za velike brojeve