题目：给定一个数字，判断是否是素数
素数概念：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数;否则称为合数。
方法一：暴力
function isPrime($num){
if($num <= 3){
return true;
}
$n = 0;
for($i=1;$i<=$n;$i++){
if($n % $i == 0){
$n++;
}
}
if($n==2){ //只有除以1和自己时
return true;
} else {
return false;
}
}
方法二：用素数表来判断素数
思路：
如果一个数不能整除比它小的任何素数，那么这个数就是素数
/**
* @param type $num 输入的要查找的数
* @param type $count 当前已知的素数个数
* @param type $primeArray 存放素数的数组
* @return int
*/
public function isPrime2($num, $count, $primeArray) {
for ($i = 0; $i < $count; $i++) {
if ($num % $primeArray[$i] == 0) {
return false;
}
}
return true;
}
public function test()
{
$num = 51;
$primeArray = [2,3,5,7];
$count = count($primeArray);
if($this->isPrime2($num, $count, $primeArray)){
echo $num .'是素数';
} else {
echo $num .'不是素数';
}
}
方法三：
思路：两个数相乘的乘积等于一个数时，那么其中一个数，肯定要小于该数的平方根
12 = 2 * 6
12 = 3 * 4
12 =*
12 = 4 * 3
12 = 6 * 2
如果在 [2,sqrt(n)] 这个区间之内没有发现可整除因子，就可以直接断定 n 是素数了，因为在区间 [sqrt(n),n] 也一定不会发现可整除因子
public function isPrime3($n)
{
if($n <= 3){ //1不是素数 2，3肯定是素数
return true;
}
for ($i = 2;$i * $i <= $n;$i++){
if ($n % $i == 0) {
return false;
}
}
return true;
}
