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