3353 - Factori 2

Cerinţa

Se dau două numere naturale. Afișați numărul pentru care produsul factorilor primi este mai mare. Dacă cele două numere au același produs al factorilor primi, afișați-l pe cel mai mic.

Date de intrare

Programul citește de la tastatură două numere naturale.

Date de ieşire

Programul va afișa pe ecran numărul cerut.

Restricții și precizări

• cele două numere citite vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

36 26

Ieșire

26

Explicație

Factorii primi ai lui 36 sunt 2 și 3, cu produsul 6. Factorii primi ai lui 26 sunt 2 și 13, cu produsul 26. Rezultatul este 26, pentru că are produsul factorilor primi mai mare.

Rezolvare

def desc(n):
    prod = 1
    d = 2
    while n > 1:
        p = 0
        while n % d == 0:
            n //= d
            p += 1
        if p:
            prod *= d
        d += 1
        if d * d > n:
            d = n
    return prod

def validate_input(a, b):
    if a < 1 or a > 10**18 or b < 1 or b > 10**18:
        return False
    return True

if __name__ == '__main__':
    a, b = map(int, input().split())
    if validate_input(a, b):
        prod1 = desc(a)
        prod2 = desc(b)
        if prod1 > prod2:
            print(a)
        elif prod1 == prod2:
            print(min(a, b))
        else:
            print(b)
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")

Explicație rezolvare

Acest program calculează produsul distinctelor prime ale numerelor date ca intrare și afișează numărul mai mare dintre cele două produse calculate. Programul include, de asemenea, o funcție de validare a datelor de intrare, care verifică dacă cele două numere sunt în intervalul [1, 10^18].

Funcția desc primește un număr întreg n și calculează produsul distinctelor prime ale acestuia, folosind o metodă numită Factorizare în factori primi. Funcția returnează produsul calculat.

În funcția principală, se citesc cele două numere de intrare a și b, iar apoi se calculează produsele distinctelor lor prime, folosind funcția desc. Se compară cele două produse calculate și se afișează numărul mai mare dintre cele două numere de intrare.

În cele din urmă, programul include o funcție de validare a datelor de intrare, care primește cele două numere de intrare și returnează False dacă cel puțin unul dintre ele este mai mic decât 1 sau mai mare decât 10^18 și True altfel. Această funcție este apelată utilizând clauza if __name__ == '__main__' pentru a asigura că datele de intrare sunt valide înainte de a fi procesate.