如何高效将正整数分解为无平方因子数与平方数的乘积？

先明确背景：你已经有能打印质因数的代码，比如针对263200，能得到它的质因数列表是2 2 2 2 2 5 5 7 47。现在要把它拆成「无平方因子数 × 某个数的平方」的形式（比如示例里的263200=658×20²），下面说下最优的实现思路。

核心逻辑 #

本质就是对每个质因数的指数做拆分：

• 每个质因数的出现次数（指数），拆成偶数部分和奇数部分。偶数部分的一半用来组成平方数的质因数，奇数部分只留1次（因为无平方因子数里每个质因数最多出现1次）。
• 拿263200的质因数举例：
  • 2出现5次：5=4+1 → 平方数里2的指数是4/2=2，无平方因子数里2留1次
  • 5出现2次：2=2+0 → 平方数里5的指数是2/2=1，无平方因子数里不带5
  • 7和47各出现1次：1=0+1 → 平方数里不带这俩，无平方因子数里各留1次
    最后平方数就是2²×5=20，无平方因子数是2×7×47=658，正好对上示例。

具体实现步骤 #

不用额外搞复杂算法，基于现有的质因数分解逻辑就能做，甚至可以边分解边处理，不用先存所有质因数，效率更高：

1. 初始化两个变量：square_part（用来凑平方数的那个数）和square_free_part（无平方因子数），初始都设为1。
2. 逐个处理质因数：
   • 先处理2：统计它在原数里的出现次数cnt。如果cnt是偶数，square_part乘上2的cnt/2次方；如果是奇数，square_part乘2的(cnt-1)/2次方，同时square_free_part乘2。
   • 再处理所有奇质数：从3开始遍历到sqrt(n)，每次统计当前质数的出现次数cnt，按上面的规则更新两个变量。
   • 最后如果剩下的n大于2，说明这是个没处理完的质因数（指数为1），直接乘到square_free_part里。
3. 输出结果：最终square_free_part就是无平方因子数，square_part的平方就是对应的平方部分。

附C++实现代码 #

#include <iostream>
#include <cmath>
using namespace std;

void decompose(int n) {
    int square_part = 1;
    int square_free_part = 1;

    // 处理质因数2
    int cnt = 0;
    while (n % 2 == 0) {
        cnt++;
        n /= 2;
    }
    if (cnt > 0) {
        square_part *= pow(2, cnt / 2);
        if (cnt % 2 != 0) {
            square_free_part *= 2;
        }
    }

    // 处理奇质因数
    for (int i = 3; i <= sqrt(n); i += 2) {
        cnt = 0;
        while (n % i == 0) {
            cnt++;
            n /= i;
        }
        if (cnt > 0) {
            square_part *= pow(i, cnt / 2);
            if (cnt % 2 != 0) {
                square_free_part *= i;
            }
        }
    }

    // 剩余的大质因数
    if (n > 2) {
        square_free_part *= n;
    }

    cout << "分解结果：" << square_free_part << " × " << square_part << "²" << endl;
}

int main() {
    int num = 263200;
    decompose(num);
    return 0;
}

运行这段代码会直接输出分解结果：658 × 20²，完全符合需求。

内容的提问来源于stack exchange，提问作者Hzastack