3315 - Eratostene3: Diferență între versiuni
Mraa (discuție | contribuții) Fără descriere a modificării |
Mraa (discuție | contribuții) Fără descriere a modificării |
||
Linia 25: | Linia 25: | ||
Divizorii lui 5, liberi de pătrate, sunt: 1, 5. | Divizorii lui 5, liberi de pătrate, sunt: 1, 5. | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | <syntaxhighlight lang="python3"> | ||
def ciurul_lui_eratostene(limit): | def ciurul_lui_eratostene(limit): |
Versiunea de la data 11 ianuarie 2024 17:23
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) + " ")