HappyCpp

一个不会打代码的程序猿

0%

分解质因数

发表于 分类于 阅读次数： 评论数：

分解质因数

分解质因数

我们由唯一分解定理可知，任何一个大于1的合数N可以唯一分解成有限个质数的乘积,即N=p1^a1 * p2^a2 * . . . * pn^an
这里p1 < p2 < p3 < … < pn，且p1~pn均为质数。
我们给出唯一分解定理的两个小应用：

1 求出数n的因子个数

公式：(1+a1) * (1+a2) * (1+a3) * . . . * (1+an)
当a1等于3时，一定有p1^0,p1^1,p1^2,p1^3这些数，再和后面的数字利用乘法定理进行组合,即可得到上面的式子。

2 求所有因子的和

公式：(p1^0 + p1^1 + … + p1^a1) * (p2^0 + p2^1 + … + p2^a2) * … * (pn^0 + pn^1 + … + pn^an)
表示选几个该因子，通过任意组合即可得到上式。

3 分解质因数

那么我们要对一个数分解质因数，只需要对这个数开始不断去除以从2开始的质数直到为1即可。
附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
int a[100005];
int main() {
	int n;
	while(scanf("%d",&n)&&n) {
		int cnt=0;
		for(int i=2; i*i<=n; i++) {
			while(n%i==0) {
				a[++cnt]=i;
				n/=i;
			}
		}
		if(n>1)
			a[++cnt]=n;
		for(int i=1; i<=cnt; i++)
			printf("%d ",a[i]);
		puts("");
	}
	return 0;
}

这里可以保证每次除以的i一定是质数，因为我们i是从小到大的，后面查找的i已经把他所包含的因子全部给筛掉了。
for循环的条件为什么是i*i<=n呢，我们都知道判断一个质数只需要判断能否被从2到sqrt(n)整除即可，这里一样，我们举例说明。
n=60，第一次我们得到2 * 2，n=15，下一步找3，3 * 3 < 15,说明至少还能找到一个3的因子，我们得到2 * 2 * 3
n=5，5 * 5 < 5,不成立，此时需要判断一下剩余的n是否大于1，若大于1说明剩余的n也为质因子之一，且它的个数为1。

练习：
附题目链接：https://codeforces.com/contest/1445/problem/C