Optimizacija provjere prostosti cijelog broja korištenjem korijena u Pythonu
U svijetu matematike, provjera je li određeni broj prost ili složen ima važnu primjenu u mnogim računalnim algoritmima i problemima. U programiranju, efikasnost provjere prostosti broja može biti ključna za brzinu izvršavanja programa, pogotovo pri radu s velikim brojevima.
Pogledajmo kako možemo optimizirati provjeru je li uneseni broj prost koristeći Python:
broj = int(input("Upišite cijeli broj:"))
jeLiProst = True
for i in range(2, int(broj ** 0.5) + 1): # Dovoljno je provjeriti do korijena 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 korijena unesenog broja, jer je dovoljno provjeriti djeljivost s brojevima do korijena 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 optimiziranu provjeru prostosti broja, što je korisno u situacijama gdje je važna brzina izvršavanja programa, posebno pri radu s velikim brojevima.