1

我已经产生了一个数字的一​​系列素因数——这应该是最难的部分！但是，为了创建相同数量的除数列表，需要以各种可能的方式组合素因数。我正在努力用 php 做的事情。

例如，我有一个数组：

2
2
2
3
3
41
53

...对于号码 156456；将它们全部相乘，你就可以得到这个数字。我需要做的是将所有的二重奏相乘，例如 2x2、2x3、2x53 等，然后将所有的三元组相乘，依此类推，直到我最终将 7 块 6 相乘。

正如你所看到的，这将给出一个非常大的数组，其中包含 4、6、8、9、12 等中的所有除数，并且有许多重复项。我似乎无法从上面的数组中得到我想要的这个除数数组。这是一个将数组中元素的每个可能组合相乘的情况，是否有一个 php 函数，我的搜索到目前为止没有结果？

4

1 回答 1

1

阅读此页面后：http://mathcentral.uregina.ca/QQ/database/QQ.02.06/joe1.html，我尝试构建一些可能有效的东西，它可能不是最有效的解决方案，它也仅限count($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表示使用哪些索引$primes来计算当前的$divisor。为了更好地展示这一点，假设$number = 5它是0000101二进制的。的计算$divisor将是2 * 1 * 2 * 1 * 1 * 1 * 1 = 4。只设置了第一位和第三位，因此仅使用数组中的第一个和第三个元素进行计算。

我希望这使它更清楚一点。

于 2013-02-08T12:41:40.823 回答