その主要な要因化を与えられた数のすべての要因を生成する

StackOverflow https://stackoverflow.com/questions/3644858

質問

すでに数の主要な要因化を持っている場合、その数のすべての要因のセットを取得する最も簡単な方法は何ですか？私は2からSQRT（n）にループして、すべての分割可能な数値を見つけることができることを知っていますが、それはすでに主要な要因を持っているので非効率的と思われます。

基本的に組み合わせ /選択関数の修正バージョンだと思いますが、私が見つけることができるのは、組み合わせの数と、実際に組み合わせ /要因を生成するのではなく、要因の数をカウントする方法だけです。

役に立ちましたか？

解決

主要な除数がバケツのボールであると想像してください。たとえば、数字の主要な除数が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);

他のヒント

DIMO414、生成因子は一般に非常に困難なタスクと見なされます。実際、あなたの重要な資産のほとんど（お金、情報など）の保護は、数を考慮するという単純で非常に困難なタスクにかかっています。 RSA暗号化スキームのこの記事を参照してください http://en.wikipedia.org/wiki/rsa_(cryptosystem）. 。私は脱線します。

あなたの質問に答えるために、Nikitaが指摘したように、組み合わせアプローチはあなたの最良の方法です（あなたの説明については称賛）。

私は2からSQRT（n）にループして、すべての分割可能な数値を見つけることができることを知っています

多くの人々は、素数の生成に関連する非常に似た概念のためにこの結論に飛びつきます。残念ながら、これは間違っています。なぜなら、素数ではないSQRT（n）よりも大きな要因をいくつか見逃しているからです（これを自分自身に証明させます）。

さて、特定の数nの因子の数を決定するために、私たちはの主要な要因化に目を向けます n. 。もしも n = pa, 、それから私たちはnが持っていることを知っています（A + 1）要因（1、p、p2, 、...、pa）。これは、因子の総数を決定するための鍵です。もしも n たとえば、複数の主要な要因がありました

n = p1a· p2b··· pkr

次に、 製品ルール カウントの（http://en.wikipedia.org/wiki/rule_of_product）、私たちはあることを知っています

m = (A + 1)·(B + 1)···(R + 1)

要因。さて、私たちがする必要があるのは、主要な要因によって与えられた数字のすべての可能な組み合わせを見つけることです。以下は、Rのいくつかのコードを示しています。これは、私が説明したことを示すことを願っています。

私のコードの最初の部分は、数値がプライムの場合、唯一の要因が1それ自体であるため、原始性の単純なチェックを行います。次に、数字がプライムで1を超えていない場合、最初に数字のプライムファクター化を見つけます。

n = p1a· p2b··· pkr

次に、ユニークなプライムのみがラベル付けされています Uniprimes、 したがって、この例では、uniprimesには（p1, 、p2, 、pk）。次に、各プライムのすべてのパワーを見つけて、それを伸びできるアレイに追加します 私のファクター。 この配列が作成された後、私はすべての要素のすべての可能な製品の組み合わせを見つけます。最後に、アレイに1を追加し（些細な要素であるため）、並べ替えます。出来上がり！それは非常に速く、多くの要因を伴う非常に多数で動作します。

コードを他の言語に対して可能な限り翻訳可能にしようとしました（つまり、プライムファクター化（または組み込み関数を使用して）生成する関数とプライムナンバーテスト関数をすでに構築していると思います）。 T 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)
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top