1

ネタバレ

これはProject Eulerの質問 3 に関するものです。答えが含まれているので、試してみたい場合は先に読まないでください。

したがって、目的は、私が書いたコードがこれを行う数値の最大の素因数を見つけることですが、数値が大きくなると失敗し、理由がわかりません。誰かが私を見てくれるかどうか疑問に思っていました. 私が考えることができる唯一のことは、数がPHPのデータ型のいくつかに対して大きすぎるということですか?

コードを貼り付けます。ローカル テスト環境がない場合は、ここにコードを貼り付けることができます: http://writecodeonline.com/php/

理論 (これを解決するためのより効率的な方法があると確信していますが、私は数学者でも流暢なコーダーでもありません) は、すべての素因数よりも大きくなければならない数から始まるということです。次に、開始番号を別の番号で順次除算しようとしました。結果が整数の場合、整数が得られなくなるまでプロセスを繰り返し実行します (素因数でなければなりません)。次に、最初の数をこの素因数で割って新しい数を取得し、最初の関数にプラグインして新しい素数と別の数を取得します。すべての数が素数になるまでこれを続けます。次に、最大の素数の簡単なチェックがあります。

それは非常に大きな数まで機能します。つまり、最大の素数としてテストする場合、(問題) でテストすると最大の素数として13195得られますが、これは正しくありません。答えはわかっているので、開始カウンターがそれよりも大きいことを確認しますが、それでも失敗します-理由がわかりません。296008514751436857

お時間をいただきありがとうございます。コードは次のとおりです（より効率的な方法があることはわかっていますが、私の方法が機能しない理由を知りたいです）。

コードは次のとおりです。

$startVal = 13195;
echo "<b>Starting Value</b> = $startVal<br /><br />";

$scriptTime = -microtime(true);

$testVar = 10000;
$primeArray = array();
$processArray = "";

function findPrimes($startStart,$startTest, array & $primeArray, $processArray) {
    $test = $startTest;
    $start = $startStart;
    $holdVal = NULL;
    for ($i=$test; $i > 1 ; $i--) { 
        if(is_int($start/$i) && $start != $i) {
            $processArray .= "$start is divisible by $i<br />";
            $start = $i;
            $i = $test +1;
        }
    }
    $processArray .= "Can't Divide Further<br /><b>Found a Prime : <font     color='red'>$start</font></b><br />";
    $primeArray[] = $start;
    if($start != $startStart) {
        $holdVal = $startStart/$start;
    }
    if(isset($holdVal)) {
        findPrimes($holdVal,$startTest,$primeArray,$processArray);
    }
    return array($primeArray,$processArray);
}

echo "Finding Primes...<br />";

$returnArray = findPrimes($startVal,$testVar,$primeArray,$processArray);
$primeArray = $returnArray[0];
$processArray = $returnArray[1];

echo "Script Found <b>".count($primeArray)."</b> Prime Numbers (";
for ($i=count($primeArray)-1; $i >= 0 ; $i--) {
    if(!$i == 0)
        echo $primeArray[$i].", ";
    else
        echo $primeArray[$i].")";
}
echo "<br />The largest Prime Factor of $startVal is <b><font     color='red'>".max($primeArray)."</font></b><br />";
$scriptTime = round(($scriptTime += microtime(true))* 1000, 3);
echo "<i>Script took $scriptTime milliseconds<br />";
echo "<br /><br /><b>Process</b><br />";
echo "<pre>";
print_r($processArray);
echo "</pre>";

また、プロセステキストビットを無視します。それを機能させることができません

4

3 に答える 3

3

数値 600851475143 は、32 ビット マシンを使用している場合に PHP で整数を使用して表現できる範囲外であるため600851475143 / 6857、整数ではありません。

php> var_dump(600851475143/6857);
float(87625999)

bcmodBC 任意精度ライブラリから割り切れるチェックを実装すると、動作させることができます。

php> echo bcmod('600851475143','6857');
0

コードでは次のようになります。

for ($i=$test; $i > 1 ; $i--) { 
    if(bcmod($start, $i) == 0 && $start != $i) {
        $processArray .= "$start is divisible by $i<br />";
        $start = $i;
        $i = $test +1;
    }
}
于 2013-04-04T20:10:45.773 に答える
2

整数オーバーフローが発生していると思われます。ターゲット番号 600851475143 は、32 ビット整数に収まらないように特別に選択されたため、この問題は大きな整数を必要とする他の問題への「ゲートウェイ」として機能します。解決策は、より大きな数値データ型を使用することです。

于 2013-04-04T20:09:17.307 に答える
1

おそらく、PHP は 32 ビット用にコンパイルされています。64 ビット OS は 32 ビット バイナリを問題なく実行します。http://php.net/manual/en/install.windows.manual.phpにアクセスして、64 ビットのバイナリがインストールされていることを確認してください。

于 2013-04-04T20:41:06.557 に答える