Here the problem is to get all 4 pairs factors of pretty big number 17309205. Results should be

{1,1,1,17309205}
{1,1,3,5769735} etc..

I tried with 4 nested for loops but it took too long, so I tried a different idea.

My way of thinking is to find every possible pairs of factors and then filter it out for those containing 4 pairs. But now I only get one result. And also the results isn't printed in t​he way it should be.

def s(target, numbers,memo={}):
    if target == 0:
        return 0
    if target == 1:
        return 1
    if target < 0:
        pass
    if target in memo:
        return memo[target]
    result = []    
    for n in numbers:
        if target%n !=0:
            pass
        else:
            dominator = target/n
            result = s(dominator, numbers, memo)
            memo[target] = [result,[n,dominator]]
            return memo[target]

v = list(range(2,17309205))
print(s(17309205,v))

CodePudding user response：

I see a possible solution. First you have to calculate all the prime factors of the number.

For that you need to create a function which yields prime numbers sequentially.

The function should store the primes in a list and test if the next non tested number is divisible by any prime in the list. If the number is not divisible by any prime in the list, then the number is prime.

For example when you have the list of primes [2,3,5,7] test divisibility of 8 by 2,3,5 and 7. It is divisible by 2 so it is not prime, then go with 9, etc... When reach 11 it is prime so put it in the list and yield 11.

Once calculated all the factor primes of the number you gave, you have to assign each factor to one of 4 places in a list. Then "put" all factors in its corrsponding place by multiplying the number in the place by the factor. You start with [1,1,1,1].

To get all 4 pair factors you need all possible assignments of factors. That is the set product of [0,1,2,3] with itself N times, where N is the number of factors.

(how many pairs are there for N factors?)

For example if there are 5 factors, then an element of the set product is [1, 0, 2, 3, 3] which assign first factor to place 1, second factor to place 0, third factor to place 2 and fourth a fifth factor to place 3.

For the set product we use itertools.product:

import itertools
assignments = itertools.product([0,1,2,3], repeat = len(factors))


for a in assignments:
    pair = [1,1,1,1]
    for i, place in enumerate(a):
        pair[place] *= factor[i]
    pairs.append(pair)

CodePudding user response：

I can get desire results with below code but the problems is being too slow if target is too big.

target = 16
for a in range(1,target 1):
    for b in range(1,target 1):
        for c in range(1, target 1):
            for d in range(1, target 1):
                if a<=b<=c<=d and a*b*c*d == target:
                    print (a,b,c,d)