Algorithm: Factorize a integer X to get as many distinct positive integers(Y1...Yk) as possible so that (Y1+1)(Y2+1)...(Yk+1) = X

Question

I recently met a algorithm question in open.kattis.com. The question's link is https://open.kattis.com/problems/listgame2. Basically, it is a question ask the players to factorize a integer X (10^3 <= X <= 10^15) to get as many distinct positive integers (Y₁,...,Y_k) as possible such that (Y₁+1)(Y₂+1)⋯(Y_k+1) = X.

I already came up with a solution using Python3, which does pass several test cases but failed one of them:MyStatus

My code is:

def minFactor(n, start):
    maxFactor = round(n**0.5)
    for i in range(start, maxFactor+1):
        if n % i == 0:
            return i
    return n

def distinctFactors(n):
    curMaxFactor = 1
    factors = []

    while n > 1:
        curMaxFactor = minFactor(n, curMaxFactor+1)
        n //= curMaxFactor
        factors.append(curMaxFactor)

    # This is for the situation where the given number is the square of a prime number
    # For example, when the input is 4, the returned factors would be [2,2] instead of [4]
    # The if statement below are used to fix this flaw
    # And since the question only requires the length of the result, deleting the last factor when repeat do works in my opinion
    if factors[-1] in factors[:-1]:
        del factors[-1]

    return factors

num = int(input())
print(len(distinctFactors(num)))

Specifically, my idea inside the above code is quite simple. For example, when the given input is 36, I run the minFactor function to find that the minimum factor of 36 is 2 (1 is ignored in this case). Then, I get 18 by doing 36/2 and invoke minFactor(18,3) since 2 is no more distinct so I start to find the minimum factor of 18 by 3. And it is 3 clearly, so I get 6 by doing 18/3 in function distinctFactors and invoke minFactor(6,4), since 4 is smaller than sqrt(6) or 6**0.5 so 6 itself will be returned and I finally get the list factors as [2,3,6], which is correct.

I have scrutinised my code and algorithm for hours but I still cannot figure out why I failed the test case, could anyone help me with my dilemma??? Waiting for reply.

Answer 1

Consider the number 2**6.11**5.

Your algorithm will find 5 factors:

2
2**2
2**3
11
11**2
(11**2 this will be discarded as it is a repeat)

A 6 length answer is:

2
2**2
11
11**2
2*11
2**2*11