黑马程序员技术交流社区

标题: 【上海校区】判断是否为质数的算法 [打印本页]

---

作者: 为热爱挥汗    时间: 2018-8-16 22:21
标题: 【上海校区】判断是否为质数的算法

判断是否为质数的算法

                                              上海传智播客  崔长春老师

先说一下什么是质数：除了1和它本身以外不再有其他因数的数称为质数。

利用程序求质数有很多理论和成熟算法，从简单的到复杂的大约有10种以上的解法，今天我们就讲解一个简单但是效率很高的算法：平方根算法。

平方根算法涉及到如下理论：

假如一个数c能分解为a*b，即c=a*b，那么a和b一定是一个小于等于c的平方根，一个大于等于c的平方根，因此我们只需要查找到c的平方根即可，如果找不到，这个数就不能分解，他就是质数。具体程序实现如下：

function getPrime($num){

                if($num==2){

                        echo "2是质数";

                }

                $tmp=sqrt($num);

                // 首先假定他是质数

                $flag=true;

                for($i=2;$i<=$tmp;$i++){

                        if($num%$i==0){

                                // 能进来，说明不是质数，将变量$flag置为false

                                $flag=false;

                                break;

                        }

                }

                // 通过判断$flag来判断是否为质数

                if($flag){

                        echo $num."是质数";

                }else{

                        echo $num."不是质数";

                }

        }

   getPrime(17);//17是质数

   getPrime(27);//27不是质数

---

作者: 不二晨    时间: 2018-9-13 16:48

很不错，受教了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2