3315 - Eratostene3 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:22:30Z

Rezolvare

← Older revision		Revision as of 18:22, 11 January 2024
Line 26:		Line 26:
	==Rezolvare==		==Rezolvare==

	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	def ciurul_lui_eratostene(limit):		def ciurul_lui_eratostene(limit):

Mraa at 17:23, 11 January 2024

2024-01-11T17:23:10Z

@@ Line 25: / Line 25: @@
 Divizorii lui 5, liberi de pătrate, sunt: 1, 5.
 ==Rezolvare==
-def ciurul_lui_eratostene(limit):
 <syntaxhighlight lang="python3">
 def ciurul_lui_eratostene(limit):

Mraa at 17:17, 11 January 2024

2024-01-11T17:17:37Z

← Older revision		Revision as of 17:17, 11 January 2024
Line 70:		Line 70:
	result = numar_divizori_liberi_de_patrate(numar, primes)		result = numar_divizori_liberi_de_patrate(numar, primes)
	file.write(str(result) + " ")		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>

Mraa: Pagină nouă: ==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 prec...

2023-12-11T15:42:44Z

Pagină nouă: ==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 prec...

New page

==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) + " ")