我有一个数字素因数的 Python 列表。我如何（Python方式）找到所有因素？

发布于 2024-09-18 02:11:59 字数 1800 浏览 14 评论 0原文

我正在研究一个欧拉项目问题，该问题需要对整数进行因式分解。我可以列出作为给定数字的因子的所有素数。算术基本定理意味着我可以使用这个列表来导出该数字的每个因数。

我当前的计划是获取基本素数列表中的每个数字并提高其幂，直到它不再是整数因子，以找到每个素数的最大指数。然后，我将乘以素数指数对的每种可能的组合。

例如，对于 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.

接下来，将这些组合进行最大指数以获得因子：

    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

因此因子列表 = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15 , 18, 20, 30, 36, 45, 60, 90, 180]

这是我到目前为止的代码。有两个问题：首先，我认为它一点也不Pythonic。我想解决这个问题。其次，我真的没有 Pythonic 方法来执行组合第二步。出于羞耻，我让你免受这组荒谬的循环的困扰。

n 是我们要分解的数字。 listOfAllPrimes 是预先计算的素数列表，最多 1000 万个。

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)

原文

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)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

苏佲洛 2024-09-25 02:11:59

考虑简单地重复每个质因数，而不是指数列表，因为它是的次数。之后，处理生成的 primefactors list-with-repetitions，itertools.combinations 正是您所需要的 - 您只需要包含长度 2 到 len(primefactors) - 1 项的组合（只有一个的组合是质因数，所有这些都将是原始数字 - 如果您也想要这些，只需使用 range(1, len(primefactors) + 1) 而不是 range(2 , len(primefactors)) 我的主要建议将使用）。

结果中将会出现重复（例如，6 将作为 12 的因子出现两次，因为后者的 primefactors 将是 [2, 2, 3]）并且它们当然可以通过通常的方式被淘汰（例如 sorted(set(results))）。

要计算给定 listOfAllPrimes 的 primefactors，请考虑以下示例：

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

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

回复收藏 0 原文

霊感 2024-09-25 02:11:59

为什么你要从一组素因数开始你的解决方案？当你对一个数字进行因式分解时，你可以很容易地得到它的所有质因数（重复的），并从中得到每个因数的指数。考虑到这一点，你可以这样写：

import itertools
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)]
# [(2, 2), (3, 2), (5, 1)]
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization]
# [[1, 2, 4], [1, 3, 9], [1, 5]]
print sorted(product(xs) for xs in itertools.product(*values))
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

get_prime_factors 和 product 这里没有实现，但你明白了（两者都写起来很简单）

恕我直言，是数学问题，欧拉问题可以使用函数式而不是命令式很好地解决（尽管我承认某些解决方案可能不会像期望的那样像 pythonic 那样出现）。

Why do you begin your solution from the set of prime factors? when you factorize a number you can as easily get all its prime factors (repeated) and from them the exponents for each factor. With this in mind, you can write this:

import itertools
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)]
# [(2, 2), (3, 2), (5, 1)]
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization]
# [[1, 2, 4], [1, 3, 9], [1, 5]]
print sorted(product(xs) for xs in itertools.product(*values))
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

get_prime_factors and product are not implemented here, but you get the idea (both are pretty simple to write)

IMHO, being mathematic problems, the Euler problems can be nicely solved using functional instead of imperative style (though I acknowledge that some solutions may not come out as pythonic as desired).

回复收藏 0 原文

戏剧牡丹亭 2024-09-25 02:11:59

您可以使用 itertools.combinations() 一旦获得重复素数列表，即可获得所有可能的因子组合，例如 180 的 [2, 2, 3, 3, 5]。然后，只需将每个组合的分量相乘即可得到一个因子。

回复收藏 0 原文

你怎么敢 2024-09-25 02:11:59

有一些更酷的 Python 功能：

def factors( num ):
    for p in primes:
        if num==1: break # stop when num is 1
        while True: # these factors may be repeated 
            new, rest = divmod(num, p) # does div and mod at once
            if rest==0: # its divisible
                yield p # current prime is factor
                num = new # continue with the div'd number
            else:
                break # no factor so break from the while


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc

With a few cooler Python features:

def factors( num ):
    for p in primes:
        if num==1: break # stop when num is 1
        while True: # these factors may be repeated 
            new, rest = divmod(num, p) # does div and mod at once
            if rest==0: # its divisible
                yield p # current prime is factor
                num = new # continue with the div'd number
            else:
                break # no factor so break from the while


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc

回复收藏 0 原文

渡你暖光 2024-09-25 02:11:59

这是原始问题的简单有效的解决方案：

def getDivisors(n):
    divisors = []
    d = 1
    while d*d < n:
        if n % d == 0:
            divisors.append(d)
            divisors.append(n / d);
        d += 1
    if d*d == n:
        divisors.append(d)
    return divisors

输出列表未排序。如果你愿意，你可以让它变得更加“Pythonic”，无论这意味着什么。

Here's a simple and efficient solution to the original problem:

def getDivisors(n):
    divisors = []
    d = 1
    while d*d < n:
        if n % d == 0:
            divisors.append(d)
            divisors.append(n / d);
        d += 1
    if d*d == n:
        divisors.append(d)
    return divisors

The output list is unsorted. You can make it more "pythonic" if you want, whatever that means.

回复收藏 0 原文

つ低調成傷 2024-09-25 02:11:59

多合一解决方案；即不需要现有的主要因素列表。

#!/usr/bin/python3 -O

from primegen import erat3 as generate_primes # see Note[1]
import operator as op, functools as ft, itertools as it

def all_factors(number):
    prime_powers= []

    for prime in generate_primes(): # for prime in listOfAllPrimes
        if prime > number: break

        this_prime_powers= [1]
        new_number, modulo= divmod(number, prime)

        while not modulo:
            number= new_number
            this_prime_powers.append(this_prime_powers[-1] * prime)
            new_number, modulo= divmod(number, prime)

        if len(this_prime_powers) > 1:
            prime_powers.append(this_prime_powers)

    # at this point:
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]]
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]]

    return sorted(
        ft.reduce(op.mul, combination, 1)
        for combination in it.product(*prime_powers))

if __name__ == "__main__":
    def num_result(number):
        return number, all_factors(number)
    print(num_result(360))
    print(num_result(210))
    print(num_result(7))

注意[1]：作为质数生成器，您可以从如何实现高效的无限生成器中选择一个Python 中的质数？或使用您自己的（例如您的listOfAllPrimes）。

这会生成一个完整的因子列表，即包括 1 和 number 参数本身。如果您想省略这些，可以使用 all_factors(number)[1:-1]。

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360])
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210])
(7, [1, 7])

An all in one solution; i.e. no need for an existing list of the prime factors.

#!/usr/bin/python3 -O

from primegen import erat3 as generate_primes # see Note[1]
import operator as op, functools as ft, itertools as it

def all_factors(number):
    prime_powers= []

    for prime in generate_primes(): # for prime in listOfAllPrimes
        if prime > number: break

        this_prime_powers= [1]
        new_number, modulo= divmod(number, prime)

        while not modulo:
            number= new_number
            this_prime_powers.append(this_prime_powers[-1] * prime)
            new_number, modulo= divmod(number, prime)

        if len(this_prime_powers) > 1:
            prime_powers.append(this_prime_powers)

    # at this point:
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]]
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]]

    return sorted(
        ft.reduce(op.mul, combination, 1)
        for combination in it.product(*prime_powers))

if __name__ == "__main__":
    def num_result(number):
        return number, all_factors(number)
    print(num_result(360))
    print(num_result(210))
    print(num_result(7))

Note[1]: As a prime number generator, you can choose one from How to implement an efficient infinite generator of prime numbers in Python? or use your own (e.g. your listOfAllPrimes).

This produces a full factor list, i.e. including 1 and the number argument itself. If you want to omit these, you can use all_factors(number)[1:-1].

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360])
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210])
(7, [1, 7])

回复收藏 0 原文

~没有更多了~