Php 质因数分解时间和大小问题

Question

素因数分解有python实现代码。 return 回答大约用了 0.1 秒。我为 php 实现了它。在大量情况下，它运行大约 3 秒（有时它永远不会 return 答案）

注意：我什至在 php 中使用了 BCMath 函数来处理非常大的数字。

注意： 该函数内的所有其他函数（如下所述）均单独测试，但其中一个函数（pollard_brent）使用php 内置函数 gmp_mod。当我运行这个：

// python handles these big numbers fine, and returns 1 for this:
echo gmp_mod(10000000000000000000001 , 2);

给我这个错误：

Message: gmp_mod(): Unable to convert variable to GMP - wrong type

我的分解代码：

public function primefactors($n, $sort = false) {
    $smallprimes = $this->primesbelow(10000);
    $factors = [];

    $limit = bcadd((bcpow($n, 0.5)) , 1);

    foreach ($smallprimes as $checker) {
        if ($checker > $limit) {
            break;
        }
        // while ($n%$checker == 0) {
        while ( bcmod($n, $checker) == 0 ) {
            array_push($factors, $checker);
            // $n = (int)($n/$checker);
            $n = bcdiv($n, $checker);
            // $limit = (int)(bcpow($n, 0.5)) + 1;
            // $limit = (bcpow($n, 0.5)) + 1;
            $limit = bcadd((bcpow($n, 0.5)) , 1);
            if ($checker > $limit) {
                break;
            }
        }
    }

    if ($n < 2) {
        return $factors;
    }

    while ($n > 1) {
        if ($this->isprime($n)) {
            array_push($factors, $n);
            // var_dump($factors);
            break;
        }
        $factor  = $this->pollard_brent($n);
        $factors = array_merge($factors, $this->primefactors($factor)); 
        $n = (int)($n/$factor);
    }
    if ($sort) {
        sort($factors);
    }

    return $factors;

}

有什么想法吗？

Answer 1

正如评论中指出的那样，手册显示两个参数都必须是 GMP 对象或数字字符串。这有效：

echo gmp_mod("10000000000000000000001", "2");

较小的数字可能会起作用，因为 PHP 会在函数内将整数转换为字符串，但是 10000000000000000000001 比 PHP_INT_MAX 长，因此它不起作用。

echo 10000000000000000000001;

产量：

1.0E+22

Php 质因数分解时间和大小问题

Php prime factorization time and size issue

php

python

int

prime-factoring