Php素因分解時間和大小問題

有一個python實施代碼素因子分解。返回答案花費了大約0.1秒。我實施了php。大量它運行大約3秒（有時它永遠不會返回答案）Php素因分解時間和大小問題

注：我甚至使用BCMath函數在PHP中處理非常大的數字。

注：此功能（如下所述）內的所有其他功能，都單獨進行測試，但在他們（pollard_brent）使用內置函數gmp_mod PHP的一個問題。當我運行此：

// 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; 

}

任何想法？

來源

2017-02-09 vahid najafi

只是一個鏡頭，但是根據手冊[gmp_mod]（https://php.net/gmp_mod），兩個參數都應該是GMP對象，而不是數字...哎呀，我需要更多地閱讀它。說一個字符串很好。但我仍然會建議嘗試使用一個實例，看看它是否有效。 –

uhhhh你甚至沒有在你的代碼中使用'gmp_mod' – cmorrissey

@JonathanKuhn但是在較小的數字中工作正常。你是什麼意思*我仍然可以建議嘗試使用實例*？你需要整個代碼嗎？ –

正如在註釋中指出的，手冊顯示這兩個參數必須是GMP對象或數字字符串。這工作：

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

較小的數字可以作爲工作PHP將整數轉換爲字符串函數中，但是10000000000000000000001長於PHP_INT_MAX所以它不會工作。

echo 10000000000000000000001;

收率：

1.0E+22

來源

2017-02-09 18:33:44 AbraCadaver

只是爲了補充一點，大數字實際上會轉換成指數爲1.0E22的浮點數，https://3v4l.org/W6kad，這對於gmp函數是錯誤的。 –

謝謝。但有一個問題。這個非常大的數字是一個整數變量，所以當我使用這個：'gmp_mod（（string）$ var，「2」）;'它給了我錯誤：'無法將變量轉換爲GMP - 字符串不是一個整數' –

Php素因分解時間和大小問題

回答

相關問題