PHP |检查一个数字是否为素数-yiteyi-C++库

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

null

例如：

Input : 21Output : Not PrimeInput : 31Output : Prime

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

简单方法： 一个简单的解决方案是迭代从2到n/2的所有数字，并对每个数字检查它是否除以n。如果我们找到任何除以的数字，我们将返回0（false），否则我们将返回1（true）。

下面是这种方法在PHP中的实现：

PHP

                         <?php                       
                         // PHP code to check whether 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"                       
                         ?>                       

输出：

Prime

时间复杂度：O（n）

有效方法： 通过观察，我们可以优化上述方法，而不是检查till n，我们可以检查till sqrt（n），因为n的较大因子必须是已检查的较小因子的倍数。因此，我们将在[2，sqrt（number）]范围内遍历，以检查该数字是否可被任何数字整除。如果它是可除的，它就不是质数。

下面是这种方法在PHP中的实现：

PHP

                         <?php                       
                         // PHP code to check whether 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"                       
                         ?>                       

输出：

Prime

时间复杂度：O（sqrt（n））

文章版权归作者所有，未经允许请勿转载。

THE END

Php