算法尽可能地考虑几个因素

Question

是否有一个已知算法将整数分解为尽可能少的因素(不一定是素数),其中每个因子都小于某个给定的常数N？

我不关心质数因子大于N的数字.而且,我不处理大于几百万的数字,并且因子分解是处理初始化的一部分,所以我并不特别担心计算复杂性.

编辑:只是为了清楚.我已经有代码找到了主要因素.我正在寻找一种方法,将这些因素结合到尽可能少的复合因子中,同时保持每个因子小于N.

Answer 1

您可以将问题分为两部分来解决问题:

1. 使用任何标准技术将您的数字分解为素数.对于只有几百万的人来说,试验部门完全没问题.

2. 取每个因子的对数,并将它们打包到大小为N的箱中.

现在,bin打包是NP-hard,但实际上可以使用简单的技术找到好的近似解决方案:first-fit算法打包不超过最佳bin数(加上一个bin)的11/9倍.

这是Python中的一个实现:

from math import exp, log, sqrt
import operator

def factorize(n):
    """
    Factorize n by trial division and yield the prime factors.

    >>> list(factorize(24))
    [2, 2, 2, 3]
    >>> list(factorize(91))
    [7, 13]
    >>> list(factorize(999983))
    [999983]
    """
    for p in xrange(2, int(sqrt(n)) + 1):
        while n % p == 0:
            yield p
            n //= p
        if n == 1:
            return
    yield n

def product(s):
    """
    Return the product of the items in the sequence `s`.

    >>> from math import factorial
    >>> product(xrange(1,10)) == factorial(9)
    True
    """
    return reduce(operator.mul, s, 1)

def pack(objects, bin_size, cost=sum):
    """
    Pack the numbers in `objects` into a small number of bins of size
    `bin_size` using the first-fit decreasing algorithm. The optional
    argument `cost` is a function that computes the cost of a bin.

    >>> pack([2, 5, 4, 7, 1, 3, 8], 10)
    [[8, 2], [7, 3], [5, 4, 1]]
    >>> len(pack([6,6,5,5,5,4,4,4,4,2,2,2,2,3,3,7,7,5,5,8,8,4,4,5], 10))
    11
    """
    bins = []
    for o in sorted(objects, reverse=True):
        if o > bin_size:
            raise ValueError("Object {0} is bigger than bin {1}"
                             .format(o, bin_size))
        for b in bins:
            new_cost = cost([b[0], o])
            if new_cost <= bin_size:
                b[0] = new_cost
                b[1].append(o)
                break
        else:
            b = [o]
            bins.append([cost(b), b])
    return [b[1] for b in bins]

def small_factorization(n, m):
    """
    Factorize `n` into a small number of factors, subject to the
    constraint that each factor is less than or equal to `m`.

    >>> small_factorization(2400, 40)
    [25, 24, 4]
    >>> small_factorization(2400, 50)
    [50, 48]
    """
    return [product(b) for b in pack(factorize(n), m, cost=product)]