2129 - Prime 1 - Revision history

Ardelean Alexandru at 15:13, 5 May 2023

2023-05-05T15:13:06Z

← Older revision		Revision as of 15:13, 5 May 2023
Line 74:		Line 74:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	#2129 Prime 1		#2129 Prime 1
			def cerinte(c, n, numere):
			if not n == len(numere):
			return False
			if not 1 < n <= 50:
			return False

			if c == 1 or c == 3:
			for nr in numere:
			if not 1 < nr < 10**7:
			return False

			return True


	def prim(nr):		def prim(nr):
			# Dace nr <= 1, atunci nr nu este prim.
	if nr < 2:		if nr < 2:
	return False		return False
			# Dacă de la 2 până la rădăcina pătrată a lui nr există un divizor a lui nr, atunci nr nu este prim.
	for i in range(2, int(nr**0.5) + 1):		for i in range(2, int(nr**0.5) + 1):
	if nr % i == 0:		if nr % i == 0:
Line 86:		Line 101:

	def suma_cifre(nr):		def suma_cifre(nr):
			# Transformăm numărul într-o listă de cifre, după care returnăm suma cifrelor
	cifre = [int(x) for x in list(str(nr))]		cifre = [int(x) for x in list(str(nr))]
	return sum(cifre)		return sum(cifre)
Line 92:		Line 108:
	def suma_factori_cifre(nr):		def suma_factori_cifre(nr):
	suma = 0		suma = 0
			# Primul factor prim este 2
	factor = 2		factor = 2

	while nr > 1:		while nr > 1:
	e = 0		exponent = 0

			# Dacă numărul este divizibil cu factorul curent...
	if nr % factor == 0:		if nr % factor == 0:
			# ...îl împărțim la factorul curent și numărăm de câte ori apare factorul curent în număr
	while nr % factor == 0:		while nr % factor == 0:
	nr //= factor		nr //= factor
	e += 1		exponent += 1
			# Adăugăm la sumă suma cifrelor factorului și a exponentului, dacă exponentul este mai mare decât 1
	suma += suma_cifre(factor)		suma += suma_cifre(factor)
	if e > 1:		if exponent > 1:
	suma += suma_cifre(e)		suma += suma_cifre(exponent)
			# Trecem la următorul factor prim
	factor += 1		factor += 1

			# Dacă factorul prim la pătrat este mai mare decât numărul, atunci numărul este prim
	if factor ** 2 > nr:		if factor ** 2 > nr:
	factor = nr		factor = nr
Line 113:		Line 135:

	def prime_suma(nr):		def prime_suma(nr):
			# Dacă nr este par sau nr-2 este prim, atunci nr nu este sumă de două numere prime.
	if nr % 2 == 0:		if nr % 2 == 0:
	return False		return False
	elif prim(nr - 2):		elif prim(nr - 2):
	return False		return False

	~~return True~~


	~~def cerinte(c, n, numere):~~
	~~if not n == len(numere):~~
	~~return False~~
	~~if not 1 < n <= 50:~~
	~~return False~~

	~~if c == 1 or c == 3:~~
	~~for nr in numere:~~
	~~if not 1 < nr < 10**7:~~
	~~return False~~

	return True		return True
Line 140:		Line 149:
	a, b = 1, 1		a, b = 1, 1

			# Generăm numere Fibonacii până ajungem la 10^7
	while a < 10 ** 7:		while a < 10 ** 7:
			# Algoritm pentru a genera numerele din șirul lui Fibonacci
	fibonacii.add(a)		fibonacii.add(a)
	temp = a		temp = a
Line 146:		Line 157:
	b += temp		b += temp

			# Pentru fiecare număr din numere...
	for numar in numere:		for numar in numere:
			# ...dacă numărul se află în șirul lui Fibonacci și este prim...
	if numar in fibonacii and prim(numar):		if numar in fibonacii and prim(numar):
			# ...îl numărăm
	nr += 1		nr += 1

Line 156:		Line 170:
	nr = 0		nr = 0
	for numar in numere:		for numar in numere:
	nd = suma_cifre(numar)		nr_suma_cifre = suma_cifre(numar)
	nde = suma_factori_cifre(numar)		nde = suma_factori_cifre(numar)

	if nd > nde:		if nr_suma_cifre > nde:
	nr += 1		nr += 1

Line 175:		Line 189:

	def prime1(c, numere):		def prime1(c, numere):
			# c este numărul cerinței
	if c == 1:		if c == 1:
	print(c_prim_fibonacii(numere))		print(c_prim_fibonacii(numere))

Ardelean Alexandru at 14:04, 29 April 2023

2023-04-29T14:04:00Z

← Older revision		Revision as of 14:04, 29 April 2023
Line 32:		Line 32:
	:2 10 13 997 233		:2 10 13 997 233
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:3		:3

Line 43:		Line 44:
	:128 25 4374 720		:128 25 4374 720
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:2		:2

Line 54:		Line 56:
	:57 30 121 11 3		:57 30 121 11 3
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:4		:4

Ardelean Alexandru: /* Rezolvare */

2023-04-29T13:42:11Z

Rezolvare

← Older revision		Revision as of 13:42, 29 April 2023
Line 71:		Line 71:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	#2129 Prime 1		#2129 Prime 1
	~~import math~~


	def prim(nr):		def prim(nr):
	if nr <~~= 1:~~		if nr < 2:
	~~return False~~
	~~if nr ==~~ 2:
	~~return True~~
	~~if nr % 2 == 0~~:
	return False		return False
			for i in range(2, int(nr**0.5) + 1):
	for i in range(3, int(~~math~~.~~sqrt(nr)~~) + 1~~, 2~~):
	if nr % i == 0:		if nr % i == 0:
	return False		return False
Line 178:		Line 171:


	def ~~main():~~		def prime1(c, numere):
	~~c = int(input())~~
	~~n = int(input())~~
	~~numere = [int(x) for x in input().split()]~~

	~~if not cerinte~~(c~~, n~~, numere):
	~~return print("Datele de intrare nu corespund restricțiilor impuse.")~~
	~~print("Datele de intrare corespund restricțiilor impuse.")~~

	if c == 1:		if c == 1:
	print(c_prim_fibonacii(numere))		print(c_prim_fibonacii(numere))
Line 198:		Line 183:

	if __name__ == "__main__":		if __name__ == "__main__":
	~~main~~()		c = int(input())
			n = int(input())
			numere = [int(x) for x in input().split()]

			if not cerinte(c, n, numere):
			print("Datele de intrare nu corespund restricțiilor impuse.")
			else:
			print("Datele de intrare corespund restricțiilor impuse.")
			prime1(c, numere)
	</syntaxhighlight>		</syntaxhighlight>

Ardelean Alexandru at 11:04, 26 March 2023

2023-03-26T11:04:56Z

← Older revision		Revision as of 11:04, 26 March 2023
Line 66:		Line 66:
	:57 -30 -121 -11 3		:57 -30 -121 -11 3
	;Ieșire		;Ieșire
	:~~Date~~ de intrare ~~gresite!~~		:Datele de intrare nu corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==

Ardelean Alexandru at 10:32, 26 March 2023

2023-03-26T10:32:54Z

← Older revision		Revision as of 10:32, 26 March 2023
Line 14:		Line 14:
	Fișierul de intrare <code>prime1.in</code> conține pe prima linie un număr natural <code>c</code> care reprezintă cerinţa (<code>1</code> , <code>2</code> sau <code>3</code>). Pe a doua linie se află numărul natural <code>n</code>. Pe a treia linie se află o secvenţă de <code>n</code> numere naturale separate prin spaţii.		Fișierul de intrare <code>prime1.in</code> conține pe prima linie un număr natural <code>c</code> care reprezintă cerinţa (<code>1</code> , <code>2</code> sau <code>3</code>). Pe a doua linie se află numărul natural <code>n</code>. Pe a treia linie se află o secvenţă de <code>n</code> numere naturale separate prin spaţii.
	==Date de ieșire==		==Date de ieșire==
	~~Fișierul~~ de ~~ieșire <code>prime1~~.~~out</code>~~ va ~~conţine o singură linie pe care va fi scris~~ răspunsul la cerinţa din fişierul de intrare.		Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

			Pe următorul rând se va afișa răspunsul la cerinţa din fişierul de intrare.

			În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

	==Restricții și precizări==		==Restricții și precizări==
Line 180:		Line 184:

	if not cerinte(c, n, numere):		if not cerinte(c, n, numere):
	return print("~~Date~~ de intrare ~~gresite!~~")		return print("Datele de intrare nu corespund restricțiilor impuse.")
			print("Datele de intrare corespund restricțiilor impuse.")

	if c == 1:		if c == 1:

Ardelean Alexandru: /* Exemplu 4 */

2023-03-20T13:25:11Z

Exemplu 4

← Older revision		Revision as of 13:25, 20 March 2023
Line 58:		Line 58:

	;Intrare		;Intrare
	:3 5 57 -30 -121 -11 3		:3
			:5
			:57 -30 -121 -11 3
	;Ieșire		;Ieșire
	:Date de intrare gresite!		:Date de intrare gresite!

Ardelean Alexandru at 13:23, 20 March 2023

2023-03-20T13:23:45Z

← Older revision		Revision as of 13:23, 20 March 2023
Line 41:		Line 41:
	:2		:2

	== Explicație ==		=== Explicație ===
	Cerinţa este 2. Succesiunea conţine două numere economice (<code>128</code> şi <code>4374</code>).		Cerinţa este 2. Succesiunea conţine două numere economice (<code>128</code> şi <code>4374</code>).

Ardelean Alexandru: Pagină nouă: ==Cerința== Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât `1` poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu: #În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? `0`, `1`, 1 2023-03-20T13:23:00Z Pagină nouă: ==Cerința== Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât <code>1</code> poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu: #În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? <code>0</code>, <code>1</code>, <code>1</... New page ==Cerința== Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât <code>1</code> poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu: #În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? <code>0</code>, <code>1</code>, <code>1</code>, <code>2</code>, <code>3</code>, <code>5</code>, <code>8</code>, <code>13</code>, <code>...</code> Este şirul în care fiecare termen, exceptând primii doi, se obţine ca suma celor doi termeni care îl precedă. #Există numere naturale denumite „economice”. Un număr natural este economic dacă numărul de cifre necesare pentru scrierea sa este mai mare decât numărul de cifre necesare pentru scrierea descompunerii sale în factori primi (adică decât numărul de cifre necesare pentru scrierea factorilor primi şi a puterilor acestora). De exemplu <code>128</code> este economic pentru că <code>128</code> se scrie cu <code>3</code> cifre, iar descompunerea sa în factori primi se scrie cu două cifre (<code>2^7</code>); <code>4374</code> este economic pentru că se scrie cu <code>4</code> cifre, în timp ce descompunerea sa în factori primi se scrie cu <code>3</code> cifre (<code>23^7</code>). Observaţi că atunci când un factor prim apare la puterea <code>1</code>, aceasta nu este necesar să fie scrisă. #Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu, <code>121</code> nu poate fi scris ca sumă de două numere prime. Scrieţi un program care citeşte numărul natural <code>n</code> şi o secvenţă de n numere naturale, apoi rezolvă următoarele cerinţe: #determină şi afişează câte dintre numerele din secvenţa dată sunt numere prime din şirul Fibonacci; #determină şi afişează câte dintre numerele din secvenţa dată sunt numere economice; #determină şi afişează câte dintre numerele din secvenţa dată nu pot fi scrise ca sumă de două numere prime. ==Date de intrare== Fișierul de intrare <code>prime1.in</code> conține pe prima linie un număr natural <code>c</code> care reprezintă cerinţa (<code>1</code> , <code>2</code> sau <code>3</code>). Pe a doua linie se află numărul natural <code>n</code>. Pe a treia linie se află o secvenţă de <code>n</code> numere naturale separate prin spaţii. ==Date de ieșire== Fișierul de ieșire <code>prime1.out</code> va conţine o singură linie pe care va fi scris răspunsul la cerinţa din fişierul de intrare. ==Restricții și precizări== <code>1 < n ≤ 50</code> Dacă <code>c=1</code> sau <code>c=3</code> numerele naturale din şir sunt mai mari decât <code>1</code> şi mai mici decât <code>10^7</code>. Dacă <code>c=2</code> numerele naturale din şir sunt mai mari decât <code>1</code> şi mai mici decât <code>10^14</code>. Pentru rezolvarea corectă a cerinţei 1 se acordă 20 de puncte; pentru rezolvarea corectă a cerinţei 2 se acordă 50 de puncte, iar pentru rezolvarea corectă a cerinţei 3 se acordă 30 de puncte. ==Exemplu 1== ;Intrare :1 :5 :2 10 13 997 233 ;Ieșire :3 ===Explicație=== Cerinţa este 1. Cele <code>3</code> numere prime din şirul Fibonacci existente în secvenţă sunt <code>2</code>, <code>13</code> şi <code>233</code>. ==Exemplu 2== ;Intrare :2 :4 :128 25 4374 720 ;Ieșire :2 == Explicație == Cerinţa este 2. Succesiunea conţine două numere economice (<code>128</code> şi <code>4374</code>). ==Exemplu 3== ;Intrare :3 :5 :57 30 121 11 3 ;Ieșire :4 ===Explicație=== Cerinţa este 3. Sunt <code>4</code> numere naturale din secvenţă care nu pot fi scrise ca sumă de două numere prime: <code>57</code>, <code>121</code>, <code>11</code>, <code>3</code>. == Exemplu 4 == ;Intrare :3 5 57 -30 -121 -11 3 ;Ieșire :Date de intrare gresite! ==Rezolvare== <syntaxhighlight lang="python" line="1"> #2129 Prime 1 import math def prim(nr): if nr <= 1: return False if nr == 2: return True if nr % 2 == 0: return False for i in range(3, int(math.sqrt(nr)) + 1, 2): if nr % i == 0: return False return True def suma_cifre(nr): cifre = [int(x) for x in list(str(nr))] return sum(cifre) def suma_factori_cifre(nr): suma = 0 factor = 2 while nr > 1: e = 0 if nr % factor == 0: while nr % factor == 0: nr //= factor e += 1 suma += suma_cifre(factor) if e > 1: suma += suma_cifre(e) factor += 1 if factor 2 > nr: factor = nr return suma def prime_suma(nr): if nr % 2 == 0: return False elif prim(nr - 2): return False return True def cerinte(c, n, numere): if not n == len(numere): return False if not 1 < n <= 50: return False if c == 1 or c == 3: for nr in numere: if not 1 < nr < 107: return False return True def c_prim_fibonacii(numere): nr = 0 fibonacii = {0} a, b = 1, 1 while a < 10 ** 7: fibonacii.add(a) temp = a a = b b += temp for numar in numere: if numar in fibonacii and prim(numar): nr += 1 return nr def c_economice(numere): nr = 0 for numar in numere: nd = suma_cifre(numar) nde = suma_factori_cifre(numar) if nd > nde: nr += 1 return nr def c_not_suma(numere): nr = 0 for numar in numere: if prime_suma(numar): nr += 1 return nr def main(): c = int(input()) n = int(input()) numere = [int(x) for x in input().split()] if not cerinte(c, n, numere): return print("Date de intrare gresite!") if c == 1: print(c_prim_fibonacii(numere)) elif c == 2: print(c_economice(numere)) elif c == 3: print(c_not_suma(numere)) if name == "main": main() </syntaxhighlight>