25

ある数の素因数分解を既に行っている場合、その数のすべての因数のセットを取得する最も簡単な方法は何ですか? 2 から sqrt(n) までループして、割り切れる数をすべて見つけることができることはわかっていますが、素因数分解が既に行われているため、非効率的です。

基本的には組み合わせ/選択関数の修正版だと思いますが、実際に組み合わせ/因子を生成するのではなく、組み合わせの数を数える方法と因子の数を数える方法しか見つけられないようです。

4

2 に答える 2

34

素約数がバケツの中のボールだと想像してください。たとえば、数の素約数が 2、2、2、3、および 7 の場合、「ボール 2」のインスタンスを 0、1、2、または 3 つ取得できます。同様に、「ボール 3」は 0 回または 1 回、「ボール 7」は 0 回または 1 回取ることができます。

ここで、「ボール 2」を 2 回、「ボール 7」を 1 回取ると、除数は 2*2*7 = 28 になります。同様に、ボールを取らない場合は除数 1 になり、すべてのボールを取る場合は除数 2 になります。 *2*2*3*7 は数値そのものに相当します。

最後に、バケツから取り出せるボールのすべての可能な組み合わせを取得するには、再帰を簡単に使用できます。

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

これで、上記の例で実行できます。

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);
于 2010-09-05T03:30:59.237 に答える
6

dimo414 では、因子の生成は一般的に非常に難しい作業と考えられています。実際、あなたの重要な資産 (つまり、お金、情報など) のほとんどを保護することは、数を因数分解するという単純ではあるが非常に困難な作業にかかっています。RSA 暗号化方式に関する記事http://en.wikipedia.org/wiki/RSA_(cryptosystem)を参照してください。余談です。

あなたの質問に答えるには、Nikitaが指摘したように、組み合わせアプローチが最善の方法です（ところで、あなたの説明を称賛します）。

2 から sqrt(n) までループして、割り切れる数をすべて見つけることができることはわかっています。

素数の生成に関連する概念が非常に似ているため、多くの人がこの結論に飛びつきます。残念ながら、素数ではない sqrt(n) より大きいいくつかの因数を見逃すことになるため、これは正しくありません (これを自分で証明してみましょう)。

ここで、任意の数 n の因数の数を決定するために、nの素因数分解を調べます。n = p a の場合、n には ( a + 1 ) 個の因数 ( 1, p, p 2 , ... , p a )があることがわかります。これは、因子の総数を決定するための鍵です。nに複数の素因数がある場合、次のようにします。

n = p 1 a · p 2 b ··· p k r

次に、カウントの製品ルール( http://en.wikipedia.org/wiki/Rule_of_product ) を使用すると、

m = ( a + 1 ) · ( b + 1 ) ··· ( r + 1 )

要因。あとは、素因数分解で得られた数の可能な組み合わせをすべて見つけるだけです。以下は、R のコードです。これは、私が説明したことを示していることを願っています。

私のコードの最初の部分では、素数の単純なチェックを行います。数値が素数の場合、因数は 1 とそれ自体だけだからです。次に、数が素数ではなく 1 より大きい場合、まず数の素因数分解を見つけます。

n = p 1 a · p 2 b ··· p k r

次に、UniPrimes とラベル付けされた一意の素数のみを見つけます。したがって、この例では、UniPrimes には ( p 1 , p 2 , p k ) が含まれます。次に、各素数のすべての累乗を見つけて、MyFactors というラベルの付いた配列に追加します。この配列が作成された後、MyFactors 内の要素のすべての可能な製品の組み合わせを見つけます。最後に、配列に 1 を追加し (これは些細な要素であるため)、並べ替えます。出来上がり！これは非常に高速で、多くの因子を持つ非常に大きな数に対して機能します。

コードをできるだけ他の言語に翻訳できるようにしました (つまり、素因数分解を生成する関数 (または組み込み関数を使用) と素数テスト関数を既に作成していると仮定します)。 R に固有の特殊な組み込み関数を使用しないでください。不明な点があればお知らせください。乾杯！

factor2 <- function(MyN) {

    CheckPrime <- isPrime(MyN)

    if (CheckPrime == F && !(MyN == 1)) {
            MyPrimes <- primeFactors(MyN)
            MyFactors <- vector()
            MyPowers <- vector()
            UniPrimes <- unique(MyPrimes)
                    for (i in 1:length(UniPrimes)) {

                            TempSize <- length(which(MyPrimes == UniPrimes[i]))

                            for (j in 1:TempSize) {
                                    temp <- UniPrimes[i]^j
                                    MyPowers <- c(MyPowers, temp)
                            }

                    }
            MyFactors <- c(MyFactors, MyPowers)
            MyTemp <- MyPowers
            MyTemp2 <- vector()
            r <- 2
            while (r <= length(UniPrimes)) {

                    i <- 1L

                    while (i <= length(MyTemp)) {
                            a <- which(MyPrimes >  max(primeFactors(MyTemp[i])))
                                    for (j in a) {
                                            temp <- MyTemp[i]*MyPowers[j]
                                            MyFactors <- c(MyFactors, temp)
                                            MyTemp2 <- c(MyTemp2, temp)
                                    }
                            i <- i + 1
                    }
                    MyTemp <- MyTemp2
                    MyTemp2 <- vector()
                    r <- r + 1
            }
    } else {
            if (MyN == 1) {
                    MyFactors <- vector()
            } else {
                    MyFactors <- MyN
            }
    }
    MyFactors <- c(1, MyFactors)
    sort(MyFactors)
}
于 2015-01-29T14:39:14.140 に答える