0

これは、後の段階で数の除算をチェックする素数を見つけるための簡単なプログラムです。

複雑さを分解するために、最初に数値の整数平方根をとることで、それを短縮しようとしました。それでも、スクリプトの実行には非常に時間がかかります。実行時間を短縮するためにコードに実装できるその他の変更 (既に最大実行時間を 5 分に設定しています)

<?php
error_reporting(E_ALL);
$num = 600851475143;
//$sqrt_num = (int)sqrt($num);

for( $j = 2; $j <= $num; $j++ )
{
    for( $k = 2; $k < $j; $k++ )
    {
        if( $j % $k == 0 )
        {
        break;
        }

    }
    if( $k == $j )
    {
        //echo "Prime Number : ", $j, "<br>";
        if( $num % $j == 0 )
        {
        echo "Prime number : ", $j, "<br>";
        }
    }
}

EDIT sqrt の行にコメントを付けたのは、これが正しいように思われるためです..しかし、それでもループには多くの時間がかかります。

4

3 に答える 3

2

コードの実行時間を改善する1つの方法は、次のとおりです。

$num = 1000;

for($j = 2; $j <= $num; $j++)
{
    $cond = sqrt($j);
    for($k = 2; $k <= $cond; $k++)
    {
        if($j % $k == 0)
        {
        break;
        }

    }
    if($k > $cond)
    {
        echo 'Prime number: ' . $j . '<br>';
    }
}

ただし、毎回最初から素数を計算する必要はありません。30秒ごとにどこにいたかを思い出し、結果をデータベース、ファイル、または配列に保存してから、スクリプトを再起動します。スクリプトは停止した場所から続行する必要があります。

于 2013-03-03T10:12:21.473 に答える
2

このコードの実行時間を短縮する最善の方法は、コードを削除することです。これを実行するたびにすべての素数を計算する必要はありません-それらはすぐに変わることはありません。

一度実行し、ファイルまたはデータベースに書き込んで、必要なときに使用します。後で使用するために、個人的に配列に入れます。

于 2013-03-03T09:57:33.353 に答える
1

試行分割による素因数分解の基本的なアルゴリズムは次のとおりです。私は PHP を知らないので、疑似コードだけを示します。

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            append f to fs
            n := n / f
        f := f + 1
    if n > 1 append n to fs
    return fs

数の因数を見つけるには、それよりも優れた方法がありますが、その単純な方法でも、解決しようとしているプロジェクト オイラーの問題には十分なはずです。1 秒以内にソリューションが得られるはずです。素数を使ったプログラミングの準備が整ったら、私のブログでこのエッセイをお勧めします。

于 2013-03-03T12:47:25.940 に答える