php中用腳本實作求素數

在電腦科學中，質數指的是只能被1和本身整除的正整數。素數可以用於加密，數學推導和演算法最佳化等領域。在實際應用中，求質數的演算法也是非常重要的知識點之一，今天我們就來探討如何用php中用腳本實現求質數。

1. 篩選法

篩選法是求質數的經典演算法，其核心思想是不斷地篩選掉不是質數的數，最後留下的就是質數。具體步驟如下：

1. 初始化一個素數數組$prime = array()，把2到n（n為要求的範圍）的數字都放進去。
2. 對於2~sqrt(n)（sqrt(n)代表n的平方根）的數字，依序判斷是否是質數，如果是，則把它的倍數從素數數組中去掉。
3. 循環結束之後，素數數組中剩下的數字就是所有的質數。

實作程式碼如下：

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));
}

2. 費馬小定理

費馬小定理是重要的數論定理，可以用來判斷一個數是否為質數。費馬小定理的陳述如下：若p是質數，a是任意整數，則a^(p-1)≡1(mod p)。

具體步驟如下：

1. 隨機選擇一個數a，判斷a和n是否互質，如果不互質則直接回傳false。
2. 計算a^(n-1) mod n的值，如果不等於1，則傳回false。
3. 經過多次測試後，如果都滿足上述兩個條件，那麼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中用腳本實作求素數的兩種方法。需要注意的是，在求解大範圍的質數時，篩選法往往比費馬小定理更有效率。

以上是php中用腳本實作求素數的詳細內容。更多資訊請關注PHP中文網其他相關文章！