检查一个数字是否为素数
给定一个数字，我们需要检查它是否是PHP中的素数。这里讨论了基本检查的一般方法。在本文中，我们将学习如何在PHP中检查一个数字是否是质数。
例子
| 1 2 3 4 5 | Input : 21 Output : Not Prime Input : 31 Output : Prime |
简易方法
一个简单的解决方案是遍历所有的数字，从2到n/2，对每个数字检查它是否除以n。
下面是这种方法在PHP中的实现:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | <?php // PHP代码检查一个数字是否是素数 // 函数检查数字是否为素数 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" ?> |
输出
| 1 | Prime |
有效的方法
我们可以通过观察来优化上述方法，而不是检查到n，我们可以检查到根号n，因为n的大因数必须是已经检查过的小因数的倍数。
因此，我们将遍历范围[2,sqrt(number)]，以检查该数字是否可被任何数字整除。如果它能被整除它不是质数。
下面是这种方法在PHP中的实现:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | <?php // PHP代码检查一个数字是否是素数 // 函数检查数字是否为素数 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" ?> |
输出
| 1 | Prime |