1409 - Numere 11

Cerinţa

Se dau n numere naturale. Calculați suma obținută prin adunarea celui mai mare divizor prim al fiecărui număr dat.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale.

Date de ieşire

Programul va afișa pe ecran numărul S, reprezentând suma ceruta.

Restricții și precizări

• 1 ≤ n ≤ 10000
• cele n numere citite vor fi mai mari decât 1 și mai mici decât 1.000.000.000

Exemplu

Intrare

9

7 30 2 17 14 10 9 3 13

Ieșire

62

Explicație

7 + 5 + 2 + 17 + 7 + 5 + 3 + 3 + 13 = 62

Rezolvare

import math

def factor_prim_maxim(n):
    d = 2
    var = 0
    while n > 1:
        p = 0
        while n % d == 0:
            p += 1
            n //= d
        if p != 0:
            var = d
        d += 1
        if d * d > n:
            if n > 1:
                var = n
            break
    return var

def validare_date(n):
    if n < 1:
        print("Intrare nevalidă! Numărul de numere întregi trebuie să fie pozitiv.")
        return False
    return True

if __name__ == '__main__':
    n = int(input("Introduceți numărul de numere întregi: "))
    if validare_date(n):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
        s = 0
        for i in range(n):
            tmp = int(input(f"Introduceți numărul întreg {i+1}: "))
            s += factor_prim_maxim(tmp)
        print(s)

Explicație rezolvare

Acest program primește de la utilizator un număr n și n numere întregi și calculează suma factorilor primi maximi ai acestor numere. Programul verifică mai întâi dacă n este pozitiv și apoi calculează factorii primi maximi pentru fiecare număr întreg dat prin intermediul unei funcții numite factor_prim_maxim. Rezultatul final este suma totală a factorilor primi maximi.