在PHP中检查一个数字是否是素数

原创 287865  2019-06-17 09:39 

给定一个数字,我们需要在PHP中检查它是否为素数。这里讨论了一般的检查方法。在本文中,我们将学习如何在PHP中检查数字是否为素数。

例子:

输入:21
输出:不是Prime

输入:31
输出:Prime

建议:在继续使用解决方案之前,请先在{IDE}上尝试您的方法。

简单方法:
一个简单的解决方案是迭代从2到n / 2的所有数字,并检查每个数字是否除以n。如果我们找到任何除数,我们返回0(假)否则我们将返回1(真)。

以下是PHP中此方法的实现:


<?php

// PHP code to check wether a number is prime or Not

// function to check the number is Prime or Not

function
primeCheck($number){

if
($number
== 1)

return
0;

for
($i
= 2; $i
<= $number/2; $i++){

if
($number
% $i
== 0)

return
0;

}

return
1;

}

 
// Driver Code

$number
= 31;

$flag
= primeCheck($number);

if
($flag
== 1)

echo
"Prime";

else

echo
"Not Prime"

?>

输出:

主要

时间复杂度:O(n)

高效方法:
我们可以通过观察优化上述方法,而不是检查直到n,我们可以检查直到sqrt(n),因为n的较大因子必须是已经检查过的较小因子的倍数。

因此,我们将在[2,sqrt(number)]范围内遍历以检查该数字是否可以被任何数字整除。如果它是可分的,那么它不是素数。

以下是PHP中此方法的实现:


<?php

// PHP code to check wether a number is prime or Not

// function to check the number is Prime or Not

function
primeCheck($number){

if
($number
== 1)

return
0;

 
for
($i
= 2; $i
<= sqrt($number); $i++){

if
($number
% $i
== 0)

return
0;

}

return
1;

}

 
// Driver Code

$number
= 31;

$flag
= primeCheck($number);

if
($flag
== 1)

echo
"Prime";

else

echo
"Not Prime"

?>

输出:

主要

时间复杂度:O(sqrt(n))

本文地址:https://www.xileso.top/571.shtml
版权声明:本文为原创文章,版权归 287865 所有,欢迎分享本文,转载请保留出处!
相关文章 关键词:

发表评论


表情