我已经生成了一个数字的素数数组——这应该是最难的部分!然而,为了创建一个相同数的除数列表,素数需要以各种可能的方式组合。我正在努力用php做一些事情。
例如,我有一个数组:
2
2
2
3
3
41
53
对于号码156456;把它们相乘,你就得到那个数字。我需要做的是将所有的二元组相乘,例如2x2、2x3、2x53等,然后将所有的三元组相乘,以此类推,直到我最终将7个6块相乘。
正如你所看到的,这将给出一个非常大的数组,其中包含4、6、8、9、12等中的所有除数,并且有许多重复项。我似乎无法从上面的数组中得到我想要的除数数组。这是一个将数组中元素的每一个可能组合相乘的例子,有php函数吗?到目前为止,我的搜索一直没有结果?
阅读本页后:http://mathcentral.uregina.ca/QQ/database/QQ.02.06/joe1.html,我试图构建一些可能有效的解决方案,它可能不是最有效的解决方法,而且也仅限于32位系统上的count($primes) <= 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
CCD_ 3的当前二进制表示表示CCD_ 4的哪些索引用于计算当前CCD_。为了更好地展示这一点,我们假设$number = 5
,它是二进制的0000101
。并且CCD_ 8的计算将是CCD_。只设置了第一个和第三个位,因此只使用数组中的第一个和第一个元素进行计算。
我希望这能让它更清楚一点。