2324 - Prim 002

Cerinţa

Anul 2017 tocmai s-a încheiat, iar nostalgicii suferă în tăcere deoarece acesta era număr prim. Dorel, un personaj întreprinzător, s-a gândit să afle pentru un număr natural n dat, care este cel mai mare divizor prim al acestuia.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul va afișa pe ecran cel mai mare divizor prim al lui n.

Restricții și precizări

1 ≤ n ≤ 10^14

Exemplu

Intrare: 2018
Ieșire: 1009

Explicație

Divizorii lui 2018 sunt 1, 2, 1009, 2018, iar cel mai mare divizor prim este 1009.

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(n):

   """Verifică dacă n se încadrează în intervalul [1, 10^14]."""
   return 1 <= n <= 10**14

def este_prim(n):

   """Verifică dacă n este un număr prim."""
   if n < 2:
       return False
   for i in range(2, int(n**0.5)+1):
       if n % i == 0:
           return False
   return True

if __name__ == '__main__':

   n = int(input("Introduceți numărul n: "))
   if not validare_date(n):
       print("Numărul introdus nu se încadrează în intervalul [1, 10^14].")
       exit()
       
   if este_prim(n):
       print(n, "este un număr prim.")
   else:
       d = 2
       max_div_prim = 1
       while n > 1:
           if n % d == 0:
               n //= d
               if este_prim(d):
                   max_div_prim = d
           else:
               d += 1
       print("Cel mai mare divizor prim al lui", n, "este", max_div_prim)

</syntaxhighlight>

Explicație rezolvare

Înainte de a începe căutarea divizorului prim, se verifică dacă numărul dat se încadrează în intervalul [1, 10^14], utilizând funcția validare_date. Dacă numărul introdus nu se încadrează în acest interval, programul afișează un mesaj de eroare și se oprește cu ajutorul funcției exit().

În caz contrar, se verifică dacă numărul este prim utilizând funcția este_prim. Dacă numărul este prim, se afișează un mesaj corespunzător.

Dacă numărul nu este prim, se caută cel mai mare divizor prim al numărului prin intermediul unui buclă while. Începând cu divizorul 2, se verifică dacă numărul dat se divide cu acesta. Dacă da, se împarte numărul la acest divizor și se verifică dacă divizorul este prim. Dacă da, divizorul este reținut ca și cel mai mare divizor prim găsit până în acel moment.

În caz contrar, se trece la următorul divizor. Procesul se repetă până când numărul dat ajunge la 1. La final, programul afișează cel mai mare divizor prim găsit, sau 1 dacă nu a fost găsit niciun divizor prim.