算法笔记 质因子分解

本文质因子分解是指将一个正整数写成一个或多个素数的乘积的形式。

由于每一个质因子都可以出现不止一次，因此不妨定义结构体 factor ，用来存放质因子及其个数。

1
2
3
4
struct factor{
	inx x;
	int cnt;  //次数
};

这样就可以通过结构体数组存放所有的质因子。

例如：

对于 180 来说，

1
2
3
fac[0].x = 2;  fac[0].cnt = 2;
fac[1].x = 3;  fac[1].cnt = 2;
fac[2].x = 5;  fac[2].cnt = 1;

即 180 = 2 * 2 * 3 * 3 * 5 。

考虑到 10 个从大到小的质数相乘（2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29），就已经超过 int 范围，因此对于一个 int 数字而言， fac 数组的大小只需要 10 就足够了。

在求素数问题上，有一个结论：一个数 n ，如果它存在约数，则约数一定成对出现，且一个大于等于根号 n ，一个小于等于根号 n 。

在求质因子上，也有一个结论：对于一个 数 n ，最多仅有一个质因子大于根号 n 。

解题思路：

  • 枚举 1 ~ sqrt(n) 范围内的所有素数，判断是否为 n 的质因子

    • 如果 p 是质因子， 在 fac 数组中增加 p ，并初始化其个数为 0 。判断 n 能否被 p 整除，若能整除，则 n 除以 p ，p的个数自增，继续判断

      1
      2
      3
      4
      5
      6
      7
      8
      9
      if (n % prime[i] == 0){
      	fac[num].x = prime[i];
      	fac[num].cnt = 0;
      	while (n % prime[i] == 0){
      		fac[num].cnt++;
      		n /= prime[i];
      	}
      	num++;
      }

    • 如果 p 不是质因子，跳过

  • 若在上面的步骤结束后 n 仍然大于 1 ，说明 n 有且仅有一个大于 sqrt(n) 的质因子，将其加入数组即可。

    1
    2
    3
    4
    if (n != 1){
    	fac[num].x = n;
    	fac[num].cnt = 1;
    }

    ​

参考

  • 算法笔记