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

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.")

Explicație rezolvare

Programul citeste de la tastatura un sir de n numere si calculeaza pentru fiecare numar din sir numarul de factori primi. Pentru a determina acest lucru, se foloseste metoda de factorizare in factori primi, adica se impart numarul iterativ cu divizorii sai primi pana cand numarul ramas este 1.

Dupa ce se calculeaza numarul de factori primi pentru fiecare numar din sir, se determina numarul cu cel mai mare numar de factori primi. Daca exista mai multe numere cu acelasi numar maxim de factori primi, se afiseaza cel mai mic dintre acestea.

Programul este validat pentru intrari corespunzatoare restrictiilor impuse prin functia "validare_date" si este apelat in blocul "if name == 'main':" pentru a asigura rularea doar in cazul in care programul este rulat direct si nu este importat ca modul intr-un alt program.