1

私は数の素因数の配列を作成しました-これは難しい部分であると思われます！ただし、同じ数の除数のリストを作成するには、可能なすべての方法で素因数を組み合わせる必要があります。私がphpで苦労していること。

たとえば、次の配列があります。

2
2
2
3
3
41
53

...番号156456の場合; それらをすべて一緒に掛けると、数に戻ります。私がする必要があるのは、すべてのデュオを一緒に乗算することです。たとえば、2x2、2x3、2x53など、次にすべてのトリプレットを一緒に乗算し、最後に6つの7つのブロックを乗算します。

ご覧のとおり、これにより、4、6、8、9、12などのすべての除数を含む非常に大きな配列が得られ、多くの重複があります。上記の配列から、必要な除数のこの配列に到達できないようです。これは、配列内の要素の可能なすべての組み合わせを乗算する場合です。このためのphp関数はありますか？これまでのところ、私の検索は無駄でしたか？

4

1 に答える 1

1

このページを読んだ後: http://mathcentral.uregina.ca/QQ/database/QQ.02.06/joe1.htmlcount($primes) <= 32 32 ビット システム。さらに必要な場合は、気軽にBitsetを使用してください。

$primes = Array(2, 2, 2, 3, 3, 41, 53);
$num_primes = count($primes); // 7, if this is over 32, it won't work on 32bit systems
$divisors = Array();

// number of possible combinations
$limit = pow(2, $num_primes) - 1; // 127

// count a number up and use the binary 
// representation to say which index is
// part of the current divisor
for($number = 0; $number <= $limit; $number++) {
    $divisor = 1;
    // only multiply activated bits in $number to the divisor
    for($i = 0; $i < $num_primes; $i++) {
        $divisor *= ($number >> $i) & 1 ? $primes[$i] : 1;
    }
    $divisors[] = $divisor;
}

echo implode(", ", array_unique($divisors));

これにより、次の除数が得られます。

1, 2, 4, 8, 3, 6, 12, 24, 9, 18, 36, 72, 41, 82, 164, 328, 123, 246, 492,
984, 369, 738, 1476, 2952, 53, 106, 212, 424, 159, 318, 636, 1272, 477,
954, 1908, 3816, 2173, 4346, 8692, 17384, 6519, 13038, 26076, 52152, 19557,
39114, 78228, 156456

すべての約数を見つけるには、可能なすべての組み合わせで各素因数を互いに乗算する必要があります。これを行うために、可能な組み合わせの数を計算します ( $limit)。この制限まで数値をカウントすると、バイナリ表現は次のようになります。

7 bit
<----->
0000000    0
0000001    1
0000010    2
0000011    3
0000100    4
0000101    5
0000110    6
0000111    7
0001000    8
0001001    9
...
1111110  126
1111111  127

の現在のバイナリ表現は、現在の の計算に使用される$numberのインデックスを表します。これをよりよく示すために、バイナリである としましょう。の計算は になります。1 番目と 3 番目のビットのみが設定されるため、配列の 1 番目と 3 番目の要素のみが計算に使用されます。$primes$divisor$number = 50000101$divisor2 * 1 * 2 * 1 * 1 * 1 * 1 = 4

これで少しわかりやすくなれば幸いです。

于 2013-02-08T12:41:40.823 に答える