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

1. Citire date de intrare

with open("eratostene4.in", "r") as file:

   n = int(file.readline().strip())
   numbers = list(map(int, file.readline().split()))

1. Calcularea divizorilor primi

max_number = max(numbers) primes = ciurul_lui_eratostene(max_number)

1. 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 lang="python3"> 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>