php - PHP与指数组合

Question

我一直在研究一个数学问题：找出大数的因数。我已经了解了“素数分解”的方法，这一切都很好地用于 php 中的代码。但是，假设我想知道数字 196 的因数（即：1、2、4、7、14、28、49、98、196），我发现这个数字的素数分解是：（ 2^2)(7^2)。

要找到这些因素，您必须在两者之间进行所有可能的组合并将它们相乘：

(2^0)(7^0) = 1
(2^1)(7^0) = 2
(2^2)(7^0) = 4
(2^0)(7^1) = 7
(2^1)(7^1) = 14
(2^2)(7^1) = 28
(2^0)(7^2) = 49
(2^1)(7^2) = 98
(2^2)(7^2) = 196

这就是我卡住的地方。我需要找到一个可以组合这些项目的函数（指数可能不会高于那个数字的素数分解）。此函数必须对 N 个因子起作用（N 是一个 > 0 且小于 100 的数字）。

我希望你能理解我的问题，并对如何解决它有一些想法！

Answer 1

以下将打印 的主要因子$N = '196'以及指数的数量。

<?php
    function is_prime($N) {
        if($N == 2) return true;
        for($i = 3 ; $i * $i <= $N; $i++ ) {
            if($N % $i == 0) return false;
        }
        return true;
    }
    $a = array();
    $N = '196';
    for($i = 2; $i <= $N; $i++) {
        while($N % $i == 0 && is_prime($i)) {
            if(!isset($a[$i])) {
                $a[$i] = 0;
            }
            $a[$i]++;
            $N = $N / $i;
        }
    }
    print_r($a);
?>