Editing 3315 - Eratostene3

==Cerința==
Se dau n numere naturale. Pentru fiecare număr aflaţi câţi divizori liberi de pătrate are acesta.

==Date de intrare==
Fișierul de intrare eratostene4.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

==Date de ieșire==
Fișierul de ieșire eratostene4.out va conține pe prima linie, pentru fiecare număr din fişierul de intrare, numărul divizorilor liberi de pătrate ai acestuia.

==Restricții și precizări==
1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000
un număr natural se numeşte liber de pătrate dacă nu se divide cu pătratul unui număr prim
==Exemplu==:
eratostene4.in

3
20 8 5
eratostene4.out

4 2 2
==Explicație==
Divizorii lui 20, liberi de pătrate, sunt: 1, 2, 5, 10.
Divizorii lui 8, liberi de pătrate, sunt: 1, 2.
Divizorii lui 5, liberi de pătrate, sunt: 1, 5.
==Rezolvare==
def ciurul_lui_eratostene(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    for i in range(int(limit**0.5) + 1, limit + 1):
        if is_prime[i]:
            primes.append(i)

    return primes

def numar_divizori_liberi_de_patrate(numar, primes):
    count = 1  # 1 este divizorul liber de pătrate
    for prime in primes:
        if prime * prime > numar:
            break
        exponent = 0
        while numar % prime == 0:
            numar //= prime
            exponent += 1
        count *= (exponent + 1)
    if numar > 1:
        count *= 2  # numărul însuși și 1
    return count - 2  # eliminăm divizorul 1 și numărul însuși

# Citire date de intrare
with open("eratostene4.in", "r") as file:
    n = int(file.readline().strip())
    numbers = list(map(int, file.readline().split()))

# Calcularea divizorilor primi
max_number = max(numbers)
primes = ciurul_lui_eratostene(max_number)

# Calcularea și afișarea rezultatelor
with open("eratostene4.out", "w") as file:
    for numar in numbers:
        result = numar_divizori_liberi_de_patrate(numar, primes)
        file.write(str(result) + " ")