算法讲解（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.吗？那么我们只需要枚举到√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;
}
发布评论