Editing 2024 - Divizor 112

== Cerinta ==

Se dă un şir format din '''n''' numere naturale nenule. Aflaţi cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

== Date de intrare ==

Fișierul de intrare '''divizor112in.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale nenule separate prin spații.

== Date de iesire ==

Fișierul de ieșire '''divizor112out.txt''' va conține pe prima linie cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

== Restrictii si precizari ==

*1 &les; n &les; 100.000
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

== Exemplul 1 ==
;divizor112in.txt
:5
:1 2 3 4 5

;divizor112out.txt
:Datele introduse corespund restrictiilor impuse
:2

== Exemplul 2 ==
;divizor112in.txt
:-4
:1000001 64 -89 43580
;divizor112out.txt
:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def get_prime_factors(num):
    factors = {}
    divisor = 2
    while num > 1:
        while num % divisor == 0:
            num //= divisor
            factors[divisor] = factors.get(divisor, 0) + 1
        divisor += 1
    return factors

def find_max_divisor(nums):
    prime_factors_count = {}
    max_divisor = None
    max_count = 0

    for num in nums:
        factors = get_prime_factors(num)
        for factor, count in factors.items():
            prime_factors_count[factor] = max(prime_factors_count.get(factor, 0), count)

    for factor, count in prime_factors_count.items():
        if count > max_count:
            max_count = count
            max_divisor = factor

    return max_divisor

def verifica_restrictii(input_file, output_file):
    # Citire date de intrare
    with open(input_file, "r") as f:
        n = int(f.readline())
        numbers = list(map(int, f.readline().split()))

    # Apelare funcție de rezolvare
    result = find_max_divisor(numbers)

    # Verificare restricții
    if 1 <= n <= 100000 and all(1 <= num < 1000000 for num in numbers):
        # Citire rezultat așteptat
        with open(output_file, "r") as g:
            result_asteptat = int(g.readline().strip())

        # Verificare rezultat
        if result == result_asteptat:
            print("Rezultat corect!")
        else:
            print("Rezultat incorect!")
            print("Rezultat așteptat:", result_asteptat)
            print("Rezultat obținut:", result)
    else:
        print("Date de intrare nevalide!")

# Citire date de intrare
with open("divizor112in.txt", "r") as f:
    n = int(f.readline())
    numbers = list(map(int, f.readline().split()))

# Apelare funcție de rezolvare
result = find_max_divisor(numbers)

# Scriere date de ieșire
with open("divizor112out.txt", "w") as g:
    g.write(str(result) + "\n")

# Apelare funcție de verificare
verifica_restrictii("divizor112in.txt", "divizor112out.txt")


</syntaxhighlight>

== Explicatie ==

2 divide două numere din şir.