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>