素因数分解された数値のすべての因数を生成する 質問する

素因数がバケツの中のボールだと想像してください。たとえば、ある数の素因数が 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);