숫자에 대해 가능한 모든 제수 곱을 생성하려면 어떻게해야합니까?

작업하는 데 필요한 크기 숫자 또는 속도가 문제인지 여부는 언급하지 않지만 여기에 작은 입력 (예 : n보다 작음)에 대해 잘 작동해야하는 매우 간단한 최적화되지 않은 솔루션이 10**7있습니다.

def products(n, min_divisor=2):
    """Generate expressions of n as a product of ints >= min_divisor."""
    if n == 1:
        yield []
    for divisor in range(min_divisor, n+1):
        if n % divisor == 0:
            for product in products(n // divisor, divisor):
                yield product + [divisor]

코드를 설명하려면이 작업을 수작업으로 체계적으로 수행하는 방법을 생각해보십시오. 포함 된 제품으로 시작할 수 있습니다 2. 경우 n홀수, 어떤이 없습니다. 경우 n도있다, 우리는 간단한 재귀를 수행 할 수의 모든 가능한 분해를 발견 n // 2하고 출력 decomposition * 2각각에 대해. 우리가 포함 된 모든 제품을 소진 한 후에 2, 우리는 관련된 제품에 대한 이동합니다 3. 그러나 여기에 추가적인 합병증이 있습니다. 첫 번째 단계에서 이미 a가 포함 된 모든 제품을 찾았 2으므로 반복적 인 솔루션을 피하기 위해 모든 제수가 최소 3. 따라서 재귀 호출은 min_divisor위 의 최소 ​​허용 제수를 추적해야합니다 . 마지막으로 기본 케이스가 필요합니다.1 빈 제품으로 표현할 수 있습니다.

놓친 경우를 n=24포함하여에 대한 출력은 다음 과 6*2*2같습니다.

>>> for product in products(24):
...     print('*'.join(map(str, product)))
... 
3*2*2*2
6*2*2
4*3*2
12*2
8*3
6*4
24

그러나 이것은 만족스럽지 않습니다. 다른 주석가들이 지적했듯이, n소인수 분해 의 곱셈 분할을 계산할 수 있어야하며 필요한 경우에만 소수를 사용하여 소인수 분해의 지수 목록에서도 계산할 수 있어야 합니다. 요인을 재구성합니다. 다음은 기존의 소인수 분해와 함께 작동하는 위의 변형입니다. 효율성 향상을위한 여지가 여전히 많이 있습니다. 특히 itertools.product사전 식적으로 작은 모든 것을 무시하기 위한 호출 및 후속 필터링 은 에서 시작min_exponents 하는 사용자 지정 반복기로 교체해야합니다 . 그러나 이것은 출발점이되어야합니다.min_exponents

import itertools

def exponent_partitions(exponents, min_exponents):
    """Generate all vector partitions of 'exponents', each of whose
    entries is lexicographically at least 'min_exponents'."""
    if all(exponent == 0 for exponent in exponents):
        yield []
    else:
        for vector in itertools.product(*(range(v+1) for v in exponents)):
            if vector >= min_exponents:
                remainder = tuple(x - y for x, y in zip(exponents, vector))
                for partition in exponent_partitions(remainder, vector):
                    yield partition + [vector]


def divisor_from_exponents(primes, exponent_vector):
    """Reconstruct divisor from the list of exponents."""
    divisor = 1
    for p, e in zip(primes, exponent_vector):
        divisor *= p**e
    return divisor


def multiplicative_partitions(primes, exponents):
    """Generate all multiplication partitions of
    product(p**e for p, e in zip(primes, exponents))"""
    if len(exponents) == 0:
        # Corner case for partitions of 1.
        yield []
    else:
        initial_vector = (0,) * (len(exponents) - 1) + (1,)
        for partition in exponent_partitions(exponents, initial_vector):
            yield [divisor_from_exponents(primes, vector) for vector in partition]

그리고의 출력 24을 다시 : 우린 쓰기 24등은 2**3 * 3**1, 그래서 소수의 튜플이다 (2, 3)와 지수의 해당 튜플이다 (3, 1).

>>> for product in multiplicative_partitions((2, 3), (3, 1)):
...     print('*'.join(map(str, product)))
... 
2*2*2*3
4*2*3
8*3
6*2*2
12*2
4*6
24

정수의 곱셈 분할을 생성하고 계산하는 방법에 대한 많은 문헌이 있습니다. 예를 들어 OEIS A001055 의 링크 와 벡터 파티션 계산을위한 SAGE 함수 를 참조하십시오 .