Get divisors of a number whose ratio is a prime number-CodePudding

I need to get all divisors of any number (up to 10e9) whose ratio is a prime number.

Consider all divisors of some integer n. Choose some of these divisors, then arrange them in a circle so that the ratio of any two adjacent numbers is a prime number. Find the maximum number of divisors of n you can choose, and find the appropriate arrangement.

For example:

input: 10
output: 1 2 10 5

2 = 1 * 2; 10 = 2 * 5; 5 = 1 * 5

Also an output array must be a cycle (circle). Therefore ratio of first and last numbers must be a prime number.

I tried to find all divisors of given number and generate all possible permutations of them and check each permutation:

from itertools import permutations

n = int(input())
d = list(filter(lambda x: not n % x, range(1, n   1)))
for i in range(1, len(d)):
    print(list(permutations(d, i)))
    # check the permutation

But it's a bad solution because it works very long. Can anyone suggest an algorithm to solve my problem more effective?

CodePudding user response：

You can solve this problem by converting it to finding the longest path in a graph (although that is NP-Hard and may not be much faster).

The graph would be formed of nodes corresponding to the factors and edges that link nodes with a prime ratio between factors.

You will first need a function that give you all the prime factors of a number (including repeating primes):

def primeFactors(N):
    d = 2
    while d*d<=N:
        while N%d==0:
            yield d
            N //= d
        d  = 1
    if N>1: yield N

You can then combine all these prime factors into a dictionary of factors where the value is a set of other factors that are at a prime ratio from each factor {factor:{factor with prime ratio}..} . This will be your graph.

def factorGraph(N):
    primes  = list(primeFactors(N))
    factors = {1:set(primes)}
    for p in primes:
        factors.update({p*f:set() for f in factors})
    for p in set(primes):
        for f in factors:
            if f%p==0:
                factors[f].add(f//p)
                factors[f//p].add(f)
    return factors

Then use a recursive function to find the longest circular path from a starting factor to a given target node (starting with the related nodes of the target node itself). The function must not use the same factor more than once so it pushes down a set of visited nodes (seen) to exclude them from the deeper search.

def longestCircle(graph,target,fromFactor=0,seen=set()):
    longest = []
    remaining = graph[fromFactor or target] - seen  # eligible next factors
    for factor in remaining:                        # Try each factor
        path = [factor]                             # form a path
        if factor != target:                        # must reach target
            path  = longestCircle(graph,target,factor,seen|{factor})
        if path[-1]==target and len(path)>=len(longest): 
            longest = path                          # keep longest path
            if len(path)==len(graph): return path   # all factors used
    return longest

Finally, the longest circular path of factors will be the one with the most elements.

def factorCircle(N):
    graph = factorGraph(N)
    return max((longestCircle(graph,first) for first in graph),key=len)

Note that this is checking from every possible starting factor in case a longer path skips one of the factors but it is likely that that 1 is always in the cycle so that may be overkill Returning longestCircle(graph,1) is probably enough but I don't have time to prove that it is (or is not).

output:

print(factorCircle(10))  # [5, 10, 2, 1]               # 4 of 4 factors
print(factorCircle(30))  # [5, 15, 30, 10, 2, 6, 3, 1] # 8 of 8
print(factorCircle(512)) # [2, 1]                      # 2 of 10
print(factorCircle(660)) 
# [5, 15, 30, 6, 66, 22, 110, 220, 44, 4, 2, 10, 20, 60, 12,
   132, 660, 330, 165, 55, 11, 33, 3, 1]               # 24 of 24