php中用脚本实现求素数-PHP问题-PHP中文网

php中用脚本实现求素数

PHPz

发布： 2023-05-07 13:02:08

原创

640人浏览过

在计算机科学中，素数指的是只能被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));
}

登录后复制

费马小定理

费马小定理是一个重要的数论定理，可以用来判断一个数是否为素数。费马小定理的表述如下：若p是质数，a是任意整数，则a^(p-1)≡1(mod p)。

具体步骤如下：

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

立即学习“PHP免费学习笔记（深入）”；

随机选择一个数a，判断a和n是否互质，如果不互质则直接返回false。
计算a^(n-1) mod n的值，如果不等于1，则返回false。
经过多次测试后，如果都满足上述两个条件，那么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中文网其它相关文章！