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

php中用脚本实现求素数

PHPz

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

原创

648人浏览过

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

具体步骤如下：

网龙b2b仿阿里巴巴电子商务平台

本系统经过多次升级改造，系统内核经过多次优化组合，已经具备相对比较方便快捷的个性化定制的特性，用户部署完毕以后，按照自己的运营要求，可实现快速定制会费管理，支持在线缴费和退费功能财富中心，管理会员的诚信度数据单客户多用户登录管理全部信息支持审批和排名不同的会员级别有不同的信息发布权限企业站单独生成，企业自主决定更新企业站信息留言、询价、报价统一管理，分系统查看分类信息参数化管理，支持多样分类信息，

查看详情

立即学习“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中文网其它相关文章！