Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - I have a Python list of the prime factors of a number. How do I (pythonically) find all the factors?

I'm working on a Project Euler problem which requires factorization of an integer. I can come up with a list of all of the primes that are the factor of a given number. The Fundamental Theorem of Arithmetic implies that I can use this list to derive every factor of the number.

My current plan is to take each number in the list of base primes and raise its power until it is no longer an integer factor to find the maximum exponents for each prime. Then, I will multiply every possible combination of prime-exponent pairs.

So for example, for 180:

Given: prime factors of 180: [2, 3, 5]
Find maximum exponent of each  factor: 
    180 / 2^1 = 90
    180 / 2^2 = 45
    180 / 2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2.

    180 / 3^1 = 60
    180 / 3^2 = 20
    180 / 3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3.

    180 / 5^1 = 36
    180 / 5^2 = 7.2 - not an integer, so 1 is the maximum exponent of 5.

Next, do every combination of these up to the maximum exponent to get the factors:

    2^0 * 3^0 * 5^0 = 1
    2^1 * 3^0 * 5^0 = 2
    2^2 * 3^0 * 5^0 = 4
    2^0 * 3^1 * 5^0 = 3
    2^1 * 3^1 * 5^0 = 6
    2^2 * 3^1 * 5^0 = 12
    2^0 * 3^2 * 5^0 = 9
    2^1 * 3^2 * 5^0 = 18
    2^2 * 3^2 * 5^0 = 36
    2^0 * 3^0 * 5^1 = 5
    2^1 * 3^0 * 5^1 = 10
    2^2 * 3^0 * 5^1 = 20
    2^0 * 3^1 * 5^1 = 15
    2^1 * 3^1 * 5^1 = 30
    2^2 * 3^1 * 5^1 = 60
    2^0 * 3^2 * 5^1 = 45
    2^1 * 3^2 * 5^1 = 90
    2^2 * 3^2 * 5^1 = 180

So the list of factors = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Here is the code I have so far. Two problems: First, I don't think it is very Pythonic at all. I'd like to fix that. Second, I really don't have a Pythonic way to do the combinatoric second step. Out of shame, I've spared you from the ridiculous set of loops.

n is the number we want to factor. listOfAllPrimes is a precalculated list of the primes up to 10 million.

def getListOfFactors(n, listOfAllPrimes):
    maxFactor = int(math.sqrt(n)) + 1
    eligiblePrimes = filter(lambda x: x <= maxFactor, listOfAllPrimes)
    listOfBasePrimes = filter(lambda x: n % x ==0, eligiblePrimes)

    listOfExponents = [] #(do I have to do this?)
    for x in listOfBasePrimes:
        y = 1
        while (x**(y+1)) % n == 0:
            y += 1
        listOfExponents.append(y)
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Instead of a list of exponents, consider simply repeating each prime factor by the number of times it is a factor. After that, working on the resulting primefactors list-with-repetitions, itertools.combinations does just what you need -- you'll just require the combinations of length 2 to len(primefactors) - 1 items included (the combinations of just one are the prime factors, that of all of them will be the original number -- if you want those too, just use range(1, len(primefactors) + 1) instead of the range(2, len(primefactors)) which my main suggestion would use).

There will be repetitions in the results (e.g., 6 will appear twice as a factor of 12, since the latter's primefactors will be [2, 2, 3]) and they can of course be weeded out in the usual ways (i.e. sorted(set(results)) for example).

To compute primefactors given listOfAllPrimes, consider for example:

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...