Editing 3605 - Desc Prime

==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==
<syntaxhighlight lang="python3" line="1">
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.")
</syntaxhighlight>