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==
 
<syntaxhighlight lang="python3" line="1">
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) + " ")
</syntaxhighlight>