Djelitelji
★☆☆ laganoIspiš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
Koji brojevi dijele 12? Je li 97 prost broj? Uz petlju i ostatak dijeljenja program to brzo provjeri.
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)
Svaki broj je djeljiv s 1 i sa samim sobom. Zato petlja ide od 1 do n, to jest range(1, n + 1).
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")
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.
True i False možemo spremiti u varijablu i koristiti kao uvjet: if prost:
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)
Djelitelji dolaze u parovima. Pogledaj broj 36:
| Manji | Veći | Umnožak |
|---|---|---|
| 1 | 36 | 36 |
| 2 | 18 | 36 |
| 3 | 12 | 36 |
| 4 | 9 | 36 |
| 6 | 6 | 36 |
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")
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.
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)
Zašto u varijabli nzd na kraju ostane baš najveći zajednički djelitelj?
Petlja ide od manjih prema većim brojevima. Svaki zajednički djelitelj prepiše prethodni, pa zadnji upisani je najveći.
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Je li 1 prost broj?
Prost broj ima točno dva djelitelja; 1 ima samo jedan.
Zašto je dovoljno provjeravati djelitelje do korijena broja?
Djelitelji dolaze u parovima d i n/d; jedan je uvijek najviše √n.
Koliko je NZD(12, 18)?
Najveći broj koji dijeli i 12 i 18 je 6.
Ispiši sve djelitelje prirodnog broja N, od najmanjeg prema najvećem.
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?
Stranica pločice mora dijeliti i A i B. Koji takav broj je najveći?
Je li zadani broj prost?
DA ako je N prost, inače NE.N može biti i milijarda, pa rješenje koje isprobava sve brojeve do N neće stići u roku. Pogledaj dio 4.
n % d == 0.d * d <= n.1 proglašen prostim · petlja od 0 (dijeljenje s nulom) · range(1, n) koji preskoči sam n · presporo rješenje za velike brojeve