0902-分解质因数+例题

天啦天啦，我突然发现我不会分解质因数，写满了一脸的方方方，马上去恶补，phew，还好炒鸡简单

核心代码

void fact(int x){
	for(int i=2;i*i<=x;++i)//每次 x 都在改变，这个循环相当于枚举小于等于 x 的所有数
//而为什么不用单独考虑质数呢？比如 i 枚举到4的时候，x 若能被4整除，
//那也会在i=2的时候把x中所有2的因子除去完，那么枚举到4的时候就不会执行下面这条语句了，
//只有在i=质数的时候，才会执行
		while(x!=i){
			if(x%i==0){
				cout<<i<<是一个质因数<<endl;
				x/=i;
			}
			else break;
		}
	cout<<x<<是一个质因数//最后的时候没被统计到
}

思路：就是数学上常用的短除法啦，用c++实现即可。我们来思考数学上怎么短除，对于一个数 x 我们每次都除以它的最小质因数，直到除出来的数为质数（不能再除）为止。那么这过程中所有的除数都是这个数 x 的质因数

比如（画板不好操作，勿嫌）

对照着程序，就懂啦~~~while的作用就是统计到这种相同的质因数

例题

就是板子题啦，只是对于阶乘，如果我们直接处理 n！的话是搞不下来的，我们就分开弄，分别处理2~n的所有质因数

【代码】

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define N 10009
using namespace std;
int p[N],n;
void fact(int x){
	for(int i=2;i<=x;++i){
		while(x!=i){
			if(x%i==0){
				p[i]++;
				x/=i;
			}
			else break;
		}
	}
	p[x]++;
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;++i)	fact(i);
	for(int i=2;i<=n;++i)
		if(p[i]) printf("%d %d\n",i,p[i]);
}

 

其实还有一种写法：
 

void fact(int x){
	for(int i=2;i*i<=x;++i){
		while(x%i==0){
			p[i]++;num++;
			x/=i;
		}
	}
	if(x!=1) num++;//两者区别不大，我就不赘述了
}