算法讲解：质数判断及质因数分解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法讲解：质数判断及质因数分解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1370字，纯文字阅读大概需要2分钟。

内容图文

算法讲解（1）：质数判断及质因数分解

目录：

1. 什么是质数

2. 什么是质因数分解

3. 算法讲解

1.什么是质数：

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

0和1不是质数

除了0,1，质数以外其他的数叫合数

例如：4不是质数，因为4的因数有1,2,4 。  2并不是1或者4，所以4不是质数，是合数

　　　3是质数，3的因数有1,3 。满足条件，所以是质数

2.什么是质因数分解：

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

质因数，顾名思义就是因数是质数

例如:18=2*3*3，其中，2,3都是质数，这就是将18分解质因数

（小学数学，不是很想多BB）

质因数分解的方法（重点？）

　　最普遍的方法：短除法

　　

当然，依旧是小学5年级数学，不多想BB

3.算法讲解

1.质数判断布尔函数Prime():

 

bool prime(int n){
    //布尔函数，false代表不是质数，true代表是负数 
    if(n<=1){
        //0,1,负数都不是质数
        return false; 
    } 
    for(int i=2;i<n;i++){
        if(n%i==0){
            //如果小于n的某一个数i是n的因数，且 i>1,则n不是质数 
            return false;
        } 
    }
    //n是质数
    return true;
}

 

2.改进后的Prime():

这里我们拿16举个例子，17=1*17，17=2*8.5,17=3*5.67,4*4.25那么还需要枚举后面的吗？后面的不就是5.67*3，8.5*2....吗？

那么我们只需要枚举到√n即可

bool prime(int n){
    //布尔函数，false代表不是质数，true代表是负数 
    if(n<=1){
        //0,1,负数都不是质数
        return false; 
    } 
    for(int i=2;i*i<n;i++){
        if(n%i==0){
            //如果小于n的某一个数i是n的因数，且 i>1,则n不是质数 
            return false;
        }  /
    }
    //n是质数
    return true;
}

 

 

 

内容总结

以上是互联网集市为您收集整理的算法讲解：质数判断及质因数分解全部内容，希望文章能够帮你解决算法讲解：质数判断及质因数分解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---