題目：給定一個數(shù)字，判斷是否是素數(shù)
素數(shù)概念：質(zhì)數(shù)又稱素數(shù)夹攒。一個大于1的自然數(shù)洒忧，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù);否則稱為合數(shù)烤惊。
方法一：暴力
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;
}
}
方法二：用素數(shù)表來判斷素數(shù)
思路：
如果一個數(shù)不能整除比它小的任何素數(shù)洪囤，那么這個數(shù)就是素數(shù)
/**
* @param type $num 輸入的要查找的數(shù)
* @param type $count 當前已知的素數(shù)個數(shù)
* @param type $primeArray 存放素數(shù)的數(shù)組
* @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 .'是素數(shù)';
} else {
echo $num .'不是素數(shù)';
}
}
方法三：
思路：兩個數(shù)相乘的乘積等于一個數(shù)時，那么其中一個數(shù)撕氧，肯定要小于該數(shù)的平方根
12 = 2 * 6
12 = 3 * 4
12 =*
12 = 4 * 3
12 = 6 * 2
如果在 [2,sqrt(n)] 這個區(qū)間之內(nèi)沒有發(fā)現(xiàn)可整除因子瘤缩，就可以直接斷定 n 是素數(shù)了，因為在區(qū)間 [sqrt(n),n] 也一定不會發(fā)現(xiàn)可整除因子
public function isPrime3($n)
{
if($n <= 3){ //1不是素數(shù) 2伦泥，3肯定是素數(shù)
return true;
}
for ($i = 2;$i * $i <= $n;$i++){
if ($n % $i == 0) {
return false;
}
}
return true;
}
