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

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.")