Avoid multiple repeat in indent

[Frankduc]

Primes up to 100 is not a big list.
Primes < 10 are 2, 3, 5, 7: 4 numbers
primes < 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97: 25 numbers

However, the number of possible combinations of these numbers grows very quickly.
Adding up all the combinations of the numbers in the primes(10) list taken 1 at a time, 2 at a time, 3 at a time and 4 at a time = 15 combinations.
The list of primes < 20 has only 8 numbers but 255 combinations.
The list of primes < 50 has 15 numbers and 32767 combinations.
The list of primes < 100 has 25 numbers and a wopping 33,554,431 combinations.

If n is the number of prime numbers, the number of combinations is 2^n - 1.

But this is not even the correct solution, because I don't see any prohibition against using 2*2*2 = 8, but (2,2,2) is not returned when you ask for all combinations of (2, 3, 5, 7) taken 3 at a time. To include combinations like (2, 2, 2) you need to use itertools.combinations_with_replacement(). Now primes < 10 has 69 combinations to test, primes < 20 has 12869 combinations, and I gave up when primes < 50 came up with 155,117,519 combinations.

I think the code below works and it is really efficient when compared to using combinations. products(100) recursively calls itself 99 times to compute the 1 product.

sums(100) calls itself 547,013 times to compute 48,899 sums. That means it finds a sum almost 1 in 10 tries. Using combinations you don't get all the sums and it only finds a sum about 1 in 1000 tries. Using combinations with replacement the hit to miss ration is probably around 1 in 1 million.

def prime_numbers(end):
    """Compute primes up to and including end using sieve of Eratosthenes algorithm"""
    primes = []
    not_primes = []
    end += 1
    for p in range(2, end):
        if p not in not_primes:
            primes.append(p)
            for np in range(p*p, end, p):
                not_primes.append(np)
    return primes

def products(target, choices, partial_product=1, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose product equals target.
    choices is list of numbers (here primes) that can be used as multiplicands.
    Save successful product lists in solutions.  Save partial product list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        products.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return products(target, choices, partial_product, [], [])

    products.count += 1
    for index, choice in enumerate(choices):
        attempt = values + [choice]
        if (product := partial_product * choice) < target:
            # Add choice as a multiplicand
            products(target, choices[index:], product, attempt, solutions)
        else:
            # Add solution if product == target.  Either way there are
            # no remaining solutions in this thread
            if product == target:
                solutions.append(attempt)
            break
    return solutions

def sums(target, choices, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose sum equals target.
    choices is list of values that can be used as addends.
    Save successful sum lists in solutions.  Save partial sum list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        sums.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return sums(target, choices, [], [])

    sums.count += 1
    sum_values = sum(values)
    for index, choice in enumerate(choices):
        # Add choice as addend
        attempt = values + [choice]
        if choice < target:
            sums(target-choice, choices[index:], attempt, solutions)
        else:
            # Add sum to solution if sum == target.  Either way there
            # are no solutions remaining in this thread.
            if choice == target:
                solutions.append(attempt)
            break
    return solutions

target = 100
primes = prime_numbers(target)
print("Products", target, products(target, primes), products.count)
print("Sums", target, len(sums(target, primes)), sums.count)

Quick reply to deanHystad. I have not review all of the code. The code you provide are always interesting and a bit sophisticated for me.
Very informative that part about Mersenne prime. Interesting: https://en.wikipedia.org/wiki/Mersenne_prime

I am not sure about that part print("Sums", target, len(sums(target, primes)), sums.count)
Sums 10 5 18
18 stands for number of times it calculates to reach 10?
What about return sums(target, choices, [], []) what use have the [] ? idexation


Thank you