0303 - Eratostene - Revision history

Csula Beatrice at 14:17, 30 April 2023

2023-04-30T14:17:06Z

← Older revision		Revision as of 14:17, 30 April 2023
Line 83:		Line 83:

	</syntaxhighlight>		</syntaxhighlight>
			==Explicaţie cod==

			Acest cod implementează Ciurul lui Eratostene, un algoritm folosit pentru a găsi toate numerele prime până la un anumit număr dat '''n'''.

			Funcția '''conform_restrictiilor''' verifică dacă datele de intrare respectă condițiile impuse și returnează vectorul de numere și '''n'''.

			Funcția '''eratostene''' primește vectorul de numere și '''n''', parcurge vectorul și pentru fiecare număr verifică dacă este prim folosind Ciurul lui Eratostene. Se verifică dacă numărul este 2, în caz contrar se începe căutarea divizorilor de la 3. Dacă numărul este divizibil cu un număr impar sau cu 2, se trece la următorul număr. În caz contrar, se continuă căutarea divizorilor până la radicalul numărului. Dacă numărul este prim, se adaugă 1 la variabila '''C'''. La final se scrie rezultatul în fișierul '''eratostene.out'''.

			În general, este important să se verifice condițiile impuse înainte de procesarea datelor pentru a preveni erori și pentru a se asigura că datele sunt valide.

Csula Beatrice at 20:44, 26 March 2023

2023-03-26T20:44:58Z

← Older revision		Revision as of 20:44, 26 March 2023
Line 47:		Line 47:
	divizor = 3		divizor = 3
	while divizor * divizor <= numar:		while divizor * divizor <= numar:
	if numar % divizor == 0:		if numar % divizor == 0 or numar%2==0:
	break		break
	divizor += 2		divizor += 2

Csula Beatrice at 20:41, 26 March 2023

2023-03-26T20:41:15Z

← Older revision		Revision as of 20:41, 26 March 2023
Line 19:		Line 19:
	: Datele sunt corecte.		: Datele sunt corecte.
	; eratostene.out		; eratostene.out
	: 4		: 3
	===Exemplul 2===		===Exemplul 2===
	; eratostene.in		; eratostene.in

Csula Beatrice: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/303/eratostene - Eratostene] ---- == Cerinţa == Se dau '''n''' numere naturale mai mici decât '''1.000.000'''. Determinaţi câte dintre ele sunt prime. == Date de intrare == Fişierul de intrare '''eratostene.in''' conţine pe prima linie numărul '''n'''; urmează cele '''n''' numere, dispuse pe mai multe linii şi separate prin spaţii. == Date de ieșire == Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt c...

2023-03-26T18:35:44Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/303/eratostene - Eratostene] ---- == Cerinţa == Se dau '''n''' numere naturale mai mici decât '''1.000.000'''. Determinaţi câte dintre ele sunt prime. == Date de intrare == Fişierul de intrare '''eratostene.in''' conţine pe prima linie numărul '''n'''; urmează cele '''n''' numere, dispuse pe mai multe linii şi separate prin spaţii. == Date de ieșire == Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt c...

New page

Sursa: [https://www.pbinfo.ro/probleme/303/eratostene - Eratostene]
----
== Cerinţa ==
Se dau '''n''' numere naturale mai mici decât '''1.000.000'''. Determinaţi câte dintre ele sunt prime.
== Date de intrare ==
Fişierul de intrare '''eratostene.in''' conţine pe prima linie numărul '''n'''; urmează cele '''n''' numere, dispuse pe mai multe linii şi separate prin spaţii.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran se va afișa:
"Datele sunt corecte.", iar apoi in fişierul de ieşire '''eratostene.out''' va conţine pe prima linie numărul '''C''', reprezentând numărul valorilor citite care erau numere prime. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1.000.000
== Exemple ==
===Exemplul 1===
; eratostene.in
: 6
: 12 18 19 25 29 7
; Ieșire
: Datele sunt corecte.
; eratostene.out
: 4
===Exemplul 2===
; eratostene.in
: 3
: 100 102 104
; Ieșire
: Datele sunt corecte.
; eratostene.out
: 0
===Exemplul 3===
; eratostene.in
: 3
: 191824719471 19991 19724174
; Ieșire
: Datele nu sunt comform restricțiilor impuse.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0303 Eratostene

def eratostene(vector, n):
C = 0
for i in range(n):
numar = vector[i]
if numar == 2:
C += 1
divizor = 3
while divizor * divizor <= numar:
if numar % divizor == 0:
break
divizor += 2
if divizor ** 2 > numar:
C += 1
f = open("eratostene.out", "w")
f.write(str(C))

def conform_restrictiilor():
vector = list()
with open('eratostene.in') as f:
lines = f.readlines()
for line in lines:
for c in line.split():
if c.isdigit() == True:
vector.append(int(c))
n = vector[0]
vector = vector[1:]
if n > 1000000 and n < 1:
print("Datele nu sunt comform restricțiilor impuse.")
exit()
for x in vector:
if x < 0 or x > 1000000:
print("Datele nu sunt comform restricțiilor impuse.")
exit()
print("Datele sunt corecte.")
return vector, n

if __name__ == '__main__':
vector, n = conform_restrictiilor()
eratostene(vector, n)

</syntaxhighlight>