当前位置:首页 > 叨叨念念 > PHP求素数(质数)

PHP求素数(质数)

叨叨念念 / 星之宇 / 2021-8-19 9:43 / 浏览:2265 / 评论:0

PHP求1000以内的素数。

素数就是大于1的自然数中除了1和本身之外没有其他公因数的数。


方案1、判断素数的办法是用1到某个数之间的所有数去除这个数,如果能够整除这个数的数超过2个那么这个数就不是素数,反之如果能够整除这个数的数只有1个或者2个,那么他就是素数。

$n=1000;
echo $n."以内的素数:";
for($m=2;$m<=$n;$m++){      //第一层循环,循环1-$n直接的所有数
    $k=0;                   //计数器初始化
    for($i=1;$i<=$m;$i++){  //第二层循环,循环1-$m直接的所有数,$m属于区间【1,$n】
        if($m%$i==0){       //取模运算,如果余数为0,K自增1
            $k++;
        }
    }
    if($k==2){              //如果k的值等于1或者2,那么是素数,将其输出
        echo $m . " ";
    }
}


方案2、判断素数的办法是除了1和本身外,有其它能够整除这个数的数,那么这个数就不是素数

$isPrime=true;
$n=1000;
echo $n."以内的素数:";
for($i=2;$i<$n;$i++){                        //第一层循环,循环1-$n直接的所有数
    for($j=2;$j<=intval(sqrt($i));$j++){     //第二层循环,$i开平方,这里的intval是10进制取整数的意思
        if($i%$j==0){                        //取模运算,如果余数为0,输出$isPrime=false,并跳出第二层循环
            $isPrime=false;
            break;
        }
        $isPrime=true;
    }
    if($isPrime){                            //如果$isPrime=true,将$i输出
        echo $i . " ";
    }
}


方案3、这个方法其实和方法二差不多,思路是同一个,实现的代码不同。

$ss = 2;                        //声明变量$ss,赋初值为最小的素数
$max = 1000;                    //声明变量$max,赋值为最大的范围
$arr = array();                 //声明一个数组$arr
echo $max."以内的素数为:";
while($ss < $max):              //判断变量是否在允许的范围内
    $boo = false;               //声明一个布尔变量$boo,初值为false
    foreach($arr as $value):    //使用foreach语句遍历$arr数组
        if($ss % $value == 0):  //如果变量$ss 能够被数组元素整除
            boo = true;         //将布尔变量赋值为true
            break;              //跳出当前循环
        endif;
    endforeach;
    if(!$boo):                  //判断变量$boo值
        echo $ss . " ";         //如果$boo为假,则说明当前变量$ss为素数,输出素数
        $arr[count($arr)] = $ss;//同时存到数组中
    endif;
    $ss++;                      //变量$ss加1
endwhile;                       //结束循环

目前有 0 条评论

    • 昵称
    • 邮箱
    • 网址