Mraa at 18:14, 11 January 2024

2024-01-11T18:14:40Z

← Older revision		Revision as of 18:14, 11 January 2024
Line 21:		Line 21:
	Sunt patru soluții: 3 17, 2 5 13, 7 13, 2 7 11. Dintre acestea, soluția care are cele mai multe numere prime și este minimă lexicografic este 2 5 13.		Sunt patru soluții: 3 17, 2 5 13, 7 13, 2 7 11. Dintre acestea, soluția care are cele mai multe numere prime și este minimă lexicografic este 2 5 13.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3" line="1">
	def is_prime(num):		def is_prime(num):
	if num < 2:
	return False		if num < 2:
	for i in range(2, int(num**0.5) + 1):		return False
	if num % i == 0:		for i in range(2, int(num**0.5) + 1):
	return False		if num % i == 0:
	return True		return False
			return True

	def generate_primes(limit):		def generate_primes(limit):
	primes = []
	for i in range(2, limit + 1):		primes = []
	if is_prime(i):		for i in range(2, limit + 1):
	primes.append(i)		if is_prime(i):
	return primes		primes.append(i)
			return primes

	def sum_of_primes(S, primes):		def sum_of_primes(S, primes):
	~~solutions = []~~

	~~def backtrack(target, path, start):~~
	~~if target == 0:~~
	~~solutions.append(path[:])~~
	~~return~~
	~~for i in range(start, len(primes)):~~
	~~if primes[i] > target:~~
	~~break~~
	~~path.append(primes[i])~~
	~~backtrack(target - primes[i], path, i + 1)~~
	~~path.pop()~~

	backtrack(S, [], 0)		solutions = []
	return solutions		def backtrack(target, path, start):
			if target == 0:
			solutions.append(path[:])
			return
			for i in range(start, len(primes)):
			if primes[i] > target:
			break
			path.append(primes[i])
			backtrack(target - primes[i], path, i + 1)
			path.pop()
			backtrack(S, [], 0)
			return solutions

	if __name__ == "__main__":		if __name__ == "__main__":
	~~try:~~
	~~S = int(input("Introduceți S: "))~~

	~~primes = generate_primes(S)~~
	~~solutions = sum_of_primes(S, primes)~~

	print(len(solutions))		try:
	if solutions:		S = int(input("Introduceți S: "))
	print(" ".join(map(str, solutions[0])))
	except ValueError:		primes = generate_primes(S)
	print("Introduceți un număr natural.")		solutions = sum_of_primes(S, primes)
			print(len(solutions))
			if solutions:
			print(" ".join(map(str, solutions[0])))
			except ValueError:
			print("Introduceți un număr natural.")
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Se dă un număr natural nenul S. Să se determine numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, precum și o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte. ==Date de intrare== Programul citește de la tastatură numărul S. ==Date de ieșire== Programul va afișa la ecran pe prima linie numărul nrSol, reprezentând numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, iar pe a doua...

2023-12-25T13:32:40Z

Pagină nouă: ==Cerința== Se dă un număr natural nenul S. Să se determine numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, precum și o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte. ==Date de intrare== Programul citește de la tastatură numărul S. ==Date de ieșire== Programul va afișa la ecran pe prima linie numărul nrSol, reprezentând numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, iar pe a doua...

New page

==Cerința==
Se dă un număr natural nenul S. Să se determine numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, precum și o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte.

==Date de intrare==
Programul citește de la tastatură numărul S.

==Date de ieșire==
Programul va afișa la ecran pe prima linie numărul nrSol, reprezentând numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, iar pe a doua linie o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte. Dacă sunt mai multe soluții, se va afișa cea minimă lexicografic, iar numerele prime din soluție se vor scrie în ordine crescătoare.

==Restricții și precizări==
1 ≤ S ≤ 100
==Exemplu==:
Intrare

20
Ieșire

4
2 5 13
==Explicație==
Sunt patru soluții: 3 17, 2 5 13, 7 13, 2 7 11. Dintre acestea, soluția care are cele mai multe numere prime și este minimă lexicografic este 2 5 13.
==Rezolvare==
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True

def generate_primes(limit):
primes = []
for i in range(2, limit + 1):
if is_prime(i):
primes.append(i)
return primes

def sum_of_primes(S, primes):
solutions = []

def backtrack(target, path, start):
if target == 0:
solutions.append(path[:])
return
for i in range(start, len(primes)):
if primes[i] > target:
break
path.append(primes[i])
backtrack(target - primes[i], path, i + 1)
path.pop()

backtrack(S, [], 0)
return solutions

if __name__ == "__main__":
try:
S = int(input("Introduceți S: "))

primes = generate_primes(S)
solutions = sum_of_primes(S, primes)

print(len(solutions))
if solutions:
print(" ".join(map(str, solutions[0])))
except ValueError:
print("Introduceți un număr natural.")

3605 - Desc Prime - Revision history

Mraa at 18:14, 11 January 2024