6

すべての因子が特定の定数N未満である場合に、整数を可能な限り少ない因子（必ずしも素数である必要はない）に因数分解する既知のアルゴリズムはありますか？

素因数がNより大きい数は気にしません。また、数百万を超える数は扱っておらず、因数分解は処理の初期化の一部であるため、計算の複雑さについては特に心配していません。

編集：明確にするために。私はすでにコードに素因数を見つけさせています。各因子をN未満に保ちながら、これらの因子を可能な限り少ない複合因子に組み合わせる方法を探しています。

4

3 に答える 3

7

問題を 2 つの部分に分割することで、問題を解決できます。

  1. 標準的な手法のいずれかを使用して、数値を素数に因数分解します。数百万の数なら、試し割りでも全然いい。

  2. 各因子の対数を取り、サイズ log Nのビンにパックします。

現在、ビン パッキングはNP 困難ですが、実際には単純な手法を使用して適切な近似解を見つけることができます。最初に適合するアルゴリズムは、最適なビン数の 11/9 倍 (および 1 つのビン) を超えてパックしません。

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)]
于 2012-09-14T13:16:15.907 に答える
1

確立されたアルゴリズムがあるかどうかはわかりませんが、次のことを試してみます

public static List<Integer> getFactors(int myNumber, int N) {
    int temp=N;
    int origNumber=myNumber;        
    List<Integer> results=new ArrayList<Integer>();
    System.out.println("Factors of "+myNumber+" not greater than "+N);
    while (temp>1) {            
        if (myNumber % temp == 0) {
            results.add(temp);
            myNumber/=temp;                                
        } else {
            if (myNumber<temp) {
                temp= myNumber;                    
            } else {
                temp--;
            }
        }
    }
    for (int div : results) {
        origNumber/=div;
    }
    if (origNumber>1) {
        results.clear();
    }        
    return(results);
}

お役に立てば幸いです。

于 2012-09-14T13:12:02.113 に答える
0

では、因数が見つかったら、それで終わりです。2 番目の因数は、最初の因数で割った数値だからです。高速化するには、素数のふるいを使用するだけです。最大数が数百万の範囲にある場合、ふるいはそれほど大きくないと思います。

于 2012-09-14T13:09:47.413 に答える