PHPでスクリプトを使用して素数を見つける-PHPの問題-php.cn

PHPでスクリプトを使用して素数を見つける

PHPz

リリース： 2023-05-07 13:02:08

オリジナル

742 人が閲覧しました

コンピュータサイエンスでは、素数は 1 とそれ自体でのみ割り切れる正の整数を指します。素数は、暗号化、数学的導出、アルゴリズムの最適化などの分野で使用できます。実際のアプリケーションでは、素数を見つけるためのアルゴリズムも非常に重要な知識ポイントの 1 つです。今日は、PHP のスクリプトを使用して素数を見つける方法について説明します。

スクリーニング方法

スクリーニング方法は、素数を見つけるための古典的なアルゴリズムです。その中心的な考え方は、素数ではない数値を継続的に除外することです。最後に残ったのは素数です。具体的な手順は次のとおりです。

素数配列 $prime = array() を初期化し、そこに 2 から n までの数値を入力します (n は必要な範囲です)。
数値 2~sqrt(n) (sqrt(n) は n の平方根を表します) について、それが素数であるかどうかを順番に判定し、素数であれば素数配列からその倍数を削除します。
ループが終了すると、素数配列の残りの数値はすべて素数になります。

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

function sieve($n) {
    $prime = array();
    for($i = 2; $i <= $n; ++$i) {
        $prime[$i] = true;
    }
    for($i = 2; $i <= sqrt($n); ++$i) {
        if($prime[$i]) {
            for($j = $i*$i; $j <= $n; $j += $i) {
                $prime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($prime));
}

ログイン後にコピー

フェルマーの小定理

フェルマーの小定理は、重要な数論の定理です。 used 数値が素数かどうかを判断します。フェルマーの小定理は次のように表されます。p が素数、a が任意の整数の場合、a^(p-1)≡1(mod p) です。

具体的な手順は次のとおりです:

数値 a をランダムに選択し、a と n が互いに素であるかどうかを判定し、互いに素でない場合は、直接 false を返します。
a^(n-1) mod n の値を計算します。1 に等しくない場合は、false を返します。
多くのテストの結果、上記の 2 つの条件が満たされる場合、n は素数である可能性が高くなります。

実装コードは次のとおりです:

function is_prime($n) {
    if($n <= 1) {
        return false;
    }
    for($i = 0; $i < 10; ++$i) {
        $a = rand(1, $n-1);
        if(gcd($a, $n) != 1) {
            return false;
        }
        if(mod_pow($a, $n-1, $n) != 1) {
            return false;
        }
    }
    return true;
}

function gcd($a, $b) {
    return ($b == 0) ? $a : gcd($b, $a%$b);
}

function mod_pow($base, $exp, $modulus) {
    $result = 1;
    while($exp > 0) {
        if($exp % 2 == 1) {
            $result = ($result * $base) % $modulus;
        }
        $exp = $exp >> 1;
        $base = ($base * $base) % $modulus;
    }
    return $result;
}

ログイン後にコピー

上記は、PHP のスクリプトを使用して素数を見つける 2 つの方法です。広範囲の素数を解く場合、スクリーニング法はフェルマーの小定理よりも効率的な場合が多いことに注意してください。

以上がPHPでスクリプトを使用して素数を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。