0111 - Nr Fact

Cerinţa

Să se scrie un program care citește un șir de n numere naturale şi determină numărul din şir care are număr maxim de factori primi.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale nenule, separate prin spaţii.

Date de ieşire

Programul afișează pe ecran numărul x, numărul din şir cu număr maxim de factori primi.

Restricții și precizări

• 0 < n < 1001
• cele n numere citite vor fi mai mici decât 2.000.000.000
• dacă în şir există mai multe numere cu număr maxim de factori primi, se va afişa cel mai mic dintre acestea

Exemplu

Intrare

5

72 30 12 75 17

Ieșire

30

Explicație

30 are trei factori primi. Celelalte numere au mai puţini factori primi.

Rezolvare

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

   factori_primi = 0
   divizor = 2
   while divizor <= n:
       if n % divizor == 0:
           factori_primi += 1
           while n % divizor == 0:
               n //= divizor
       divizor += 1
   return factori_primi

def validare_date(n, sir_numere):

   if n < 1 or n > 1000:
       return False
   for numar in sir_numere:
       if numar <= 0 or numar >= 2000000000:
           return False
   return True

if __name__ == '__main__':

   n = int(input("Introduceti numarul de numere din sir: "))
   sir_numere = list(map(int, input("Introduceti numerele separate prin spatii: ").split()))
   if validare_date(n, sir_numere):
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
       max_factori_primi = 0
       numar_max_factori_primi = sir_numere[0]

       for numar in sir_numere:
           factori_primi = numar_factori_primi(numar)
           if factori_primi > max_factori_primi:
               max_factori_primi = factori_primi
               numar_max_factori_primi = numar
           elif factori_primi == max_factori_primi and numar < numar_max_factori_primi:
               numar_max_factori_primi = numar

       print(f"Numarul cu cel mai mare numar de factori primi este: {numar_max_factori_primi}")
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Acest cod verifică validitatea datelor de intrare și apoi găsește numărul dintr-un șir de numere care are cel mai mare număr de factori primi. Funcția numar_factori_primi(n) calculează numărul de factori primi ai unui număr, iar funcția validare_date(n, sir_numere) verifică dacă datele introduse sunt valide. Dacă datele sunt valide, programul găsește numărul din șir care are cel mai mare număr de factori primi și îl afișează.