Efikasna provjera prostosti cijelog broja u Pythonu
U svijetu matematike, provjera je li određeni broj prost ili složen igra važnu ulogu u mnogim računalnim algoritmima i problemima. U programiranju, postoji više načina za provjeru prostosti broja, a odabir odgovarajuće metode može značajno utjecati na učinkovitost programa.
Pogledajmo kako možemo efikasno provjeriti je li uneseni broj prost koristeći Python:
broj = int(input("Upišite cijeli broj:"))
jeLiProst = True
for i in range(2, broj // 2): # Dovoljno je doći do polovice broja
if broj % i == 0:
jeLiProst = False
break # Prisilno prekidanje for petlje
if jeLiProst:
print("Broj je prost!")
else:
print("Broj je složen!")
U ovom kodu, korisnik unosi cijeli broj koji želi provjeriti je li prost ili složen. Umjesto provjere svih brojeva do samog broja, koristimo samo raspon od 2 do polovice unesenog broja jer je dovoljno provjeriti djeljivost s brojevima do polovice kako bismo odredili je li broj prost. Ako se broj dijeli bez ostatka s bilo kojim brojem u tom rasponu, označava se kao složen i petlja se prekida. Ako se broj ne dijeli ni s jednim brojem u rasponu, označava se kao prost.
Ovaj pristup omogućuje efikasnu provjeru prostosti broja, što je korisno u situacijama gdje je važna brzina izvršavanja programa ili kada se radi s velikim brojevima.