0462 - Div Prim Max

Cerinţa

Se citesc numere de la tastatură până când se introduc două numere egale. Să se determine numărul citit cu număr maxim de divizori primi.

Date de intrare

Programul citește de la tastatură numere întregi. Citirea se încheie când se introduc două numere egale.

Date de ieşire

Programul afișează pe ecran numerele M NRDIV, separate printr-un spațiu, reprezentând numărul citit cu număr maxim de divizori primi și numărul de divizori primi ai săi.

Restricții și precizări

• numerele citite sunt numere naturale mai mici decât 1.000.000.000
• dacă există mai multe numere cu număr maxim de divizori primi, se va afişa cel mai mare dintre ele

Exemplu

Intrare

15 30 24 17 84 42 108 20 20

Ieșire

84 3

Explicație

Numerele 30 84 42 au câte 3 divizori primi, și nu există printre numerele date numere cu mai mulți divizori primi. Dintre acestea, cel mai mare este 84.

Rezolvare

import math

def nrdiv(x):
    d = 2
    cnt = 0
    while x > 1:
        p = 0
        while x % d == 0:
            p += 1
            x //= d
        if p > 0:
            cnt += 1
        d += 1
        if d * d > x:
            d = x
    return cnt

def validare_date(numar):
    while True:
        try:
            n = int(input(f"Introduceți {numar} număr: "))
            if n <= 0:
                raise ValueError("Numărul trebuie să fie pozitiv.")
            return n
        except ValueError as e:
            print(f"Input invalid: {e}")

if __name__ == '__main__':
    a = validare_date("primul")
    nmax = a
    max_div = nrdiv(a)
    while True:
        b = validare_date("următorul")
        if a == b:
            break
        div_b = nrdiv(b)
        if div_b > max_div:
            max_div = div_b
            nmax = b
        elif div_b == max_div and b > nmax:
            nmax = b
        a = b
    print(f"Numărul cu cei mai multi divizori este: {nmax} cu {max_div} divizori.")
    print("Datele de intrare corespund restricțiilor impuse.")

Explicație rezolvare

Pentru a rezolva problema, trebuie să parcurgem secvența dată și să numărăm divizorii fiecărui element. Dacă numărul de divizori al unui element este mai mare decât cel al celorlalte elemente întâlnite până în acel moment, actualizăm numărul maxim de divizori și numărul corespunzător. Dacă numărul de divizori al elementului curent este egal cu numărul maxim de divizori întâlnit până acum, comparam elementul curent cu cel mai mare număr găsit până acum și actualizăm numărul corespunzător dacă este cazul. Pentru a număra divizorii unui număr, parcurgem toate numerele mai mici sau egale cu rădăcina pătrată a numărului respectiv și verificăm dacă sunt divizori sau nu. Pentru a gestiona citirea datelor de intrare, folosim o funcție de validare a datelor care verifică dacă valorile introduse sunt numere întregi pozitive.