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}$ 的因子。证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕

基于上面的两条结论，只要从1~ $\sqrt{n}$ 把每个数都除一遍，除尽除完，最后剩下的数如果不为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;
}

优化思路：

我们不去枚举每个数，而是枚举每个质因子，看下在2~n中每个质因子出现的次数

在1x2x3x4x5x6x......x n-1 x n其中

能够被2整除的数有：

1*2 2*2 3*2....... i*2 其中2*i<=n 个数 i=n/2

能够被 ${2}^{2}$ 整除的数有:

1* ${2}^{2}$ 2* ${2}^{2}$ 3* ${2}^{2}$ ......i* ${2}^{2}$ 其中i* ${2}^{2}$ <=n 个数i=n/ ${2}^{2}$

...........

在统计被2整除的个数时，相当于把每个数都除了2，剩下的数还有可能被2整除那些数是 ${2}^{2}$ 的数， ${2}^{2}$ 的数有n/ ${2}^{2}$ 个，剩下的数还有可能被2整除，那些数是 ${2}^{3}$ 的数， ${2}^{3}$ 的数有n/ ${2}^{3}$ 个，............所以2作为因子的个数为

$\frac{n}{2}+\frac{n}{{2}^{2}}+\frac{n}{{2}^{3}}.........+\frac{n}{{2}^{p}}$ 其中 ${2}^{p}<=n$

同理3作为因子的个数为：

$\frac{n}{3}+\frac{n}{{3}^{2}}+\frac{n}{{3}^{3}}.........+\frac{n}{{3}^{p}}$ 其中 ${3}^{p}<=n$

等等

所以只要枚举每个质数，使用循环在求出该质数作为因子的个数即可，每个质数求解时，

p= $\log_{2}{n}$ ,质数的个数为 $\frac{n}{\ln n}$ ，因此总的时间复杂度为 $\log_{2}{n}$ * $\frac{n}{\ln n}$ = $\frac{\ln{n}}{\ln{2}}$ * $\frac{n}{\ln n}$ = $\frac{n}{\ln{2}}$ ，即时间复杂度为O(n)