02 分解质因子-Toy模板网

这篇具有很好参考价值的文章主要介绍了02 分解质因子。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、数n的质因子分解

题目描述：

输入一个数n（n<=10^6）,将数n分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入 5

输出 5 1

输入 10

输出 2 1 5 1

朴素解法：

首先求出1~n的所有质数，每个质数每个质数的进行去除，要保证n中除尽除完，直到把n除到1为止。

程序实现：

#include<bits/stdc++.h>

using namespace std;

const int N=1e6;

int prime[N],idx;
bool st[N];

void init(){
	for(int i=2;i<N;i++){
		if(!st[i]) prime[++idx]=i;
		for(int j=1;prime[j]*i<N;j++){
			st[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int main(){
	init();
	int n;
	cin>>n;
	if(!st[n]) cout<<n<<" "<<1<<endl;
	else{
		for(int i=1;prime[i]<=n&&i<=idx;i++){
			int p=prime[i];
			int sum=0;
			while(n%p==0){
				sum++;
				n/=p;
			}
			if(sum) cout<<p<<" "<<sum<<endl;
		}
	}
	return 0;
}

优化思路：

其一：n如果除掉了前面的某个质因子，后面不能再被某个质因子的倍数整除了，证明比较简单，使用反证法就可以。

其二：n中最多只含有一个大于的因子。证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕

基于上面的两条结论，只要从1~把每个数都除一遍，除尽除完，最后剩下的数如果不为1，这个数就是最大的质因子

代码实现

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	for(int i=2;i<=n/i;i++){
		int sum=0;
		while(n%i==0){
			sum++;
			n/=i;
		}
		if(sum) cout<<i<<" "<<sum<<endl;
	}
	if(n!=1) cout<<n<<" "<<1<<endl;
	return 0;
}

二、阶乘的质因子分解

题目描述

题目分析：

我们枚举1∼n的所有数，把每一个数的质因子加到一个数组里。
最后输出质因子数量大于0的数。时间复杂度为O(n^2/ln n)

程序实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int prime[N],idx;
bool st[N];

void init(){
	for(int i=2;i<N;i++){
		if(!st[i]) prime[++idx]=i;
		for(int j=1;prime[j]*i<N;j++){
			st[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int ans[N];  //ans[i]表示第i个质因子的个数
int main(){
	init();
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){  //枚举每一个数
		for(int j=1;prime[j]<=i&&j<=idx;j++){
			int p=prime[j];
			int cur=i;
			while(cur%p==0){
				ans[j]++;
				cur/=p;
			}
		}
	}
	for(int i=1;i<=idx;i++){
		if(ans[i]) cout<<prime[i]<<" "<<ans[i]<<endl;
	}
	
	return 0;
}