题解 | 分解质因数

#include <stdio.h>

int main() {
   long long n;
    scanf("%lld", &n);
    
    // 处理质因数2
    while (n % 2 == 0) {
        printf("2 ");
        n /= 2;
    }
    
    // 处理质因数3
    while (n % 3 == 0) {
        printf("3 ");
        n /= 3;
    }
    
    // 处理其他质因数（6k±1形式）
    long long f = 5;
    int first = 1;  // 标记是否是第一个输出的质因数
    
    // 优化：只在f的平方不超过n时循环
    while (f * f <= n) {
        if (n % f == 0) {
            // 如果是第一个质因数且之前没有输出过，直接输出（避免多余空格）
            if (first) {
                printf("%lld", f);
                first = 0;
            } else {
                printf(" %lld", f);
            }
            n /= f;
        } else {
            // 根据当前f值决定步长（2或4）
            if (f % 6 == 5) {
                f += 2;
            } else {
                f += 4;
            }
        }
    }
    
    // 处理剩余的质因数
    if (n > 1) {
        if (first) {
            printf("%lld", n);
        } else {
            printf(" %lld", n);
        }
    }
    return 0;
}