【普及】关于质因子（因子）的总结
Daniel_yao
·
2022-01-28 13:16:07
·
个人记录
1. 质因子分解的意义：
可以帮助我们解决一些求最大公因数和最小公倍数的问题；
可以帮助我们判断该数是质数还是合数；
2. 适用题型：
求一个数的阶乘时，当这个数很大，longlong 都存不下的时候，就可以使用分解质因数法（分解因数即可，并非一定要分解质因数）来逐一判断；
判断一个数是质数还是合数的时候，可以使用分解质因数法，如果这个数的因子有且只有它本身，说明它是质数，反之则是合数；
求最大公约数和最小公倍数的时候，也可以用到分解质因数的方法，最小公倍数即是两数的最小共同因子，最大公倍数即是两数的最大公因子之积；
3. 实战：
辗转相除法
(虽然跑题但很实用的一种求最大公约数的方法)
int gcd(int a,int b){//欧几里得公式
if(a % b == 0) {//mod到最后为0，除数便是最大公约数
return b;
}
return gcd(b, a % b);// 函数递归
}
判断质数
bool zhi(int x){
if(x < 2){//剪枝
return false;
}
//枚举x的所有因子，判断是否为质数
for(int i = 2;i * i /*再来剪枝*/ <= x;i++){
if(x % i == 0){//如果x能被i(x的因子)整除；
return false;
}
}
//如果x没有一个能被整除的i(除了本身)，说明它是质数；
return true;
}
但这样筛素数显然没有埃氏和欧拉筛好用
阶乘
for(int i = 2;i <= n;i++){//枚举n的所有可能因子
while(n % i == 0){//如果n mod i为0，即i是n的因子
n /= i; //除掉；
...//这里即可按题目要求判断
...
...
}
...
}
这几个模板都运用到了质因子和因子，可以看出质因子是多么的重要
4. Finish!!!
记得双击，点赞，加关注！