C语言如何进行质因数分解

在C语言中，质因数分解通常涉及找到一个给定整数的所有因子，然后筛选出那些唯一的质数因子。下面是一个简单的示例，展示了如何进行质因数分解：

#include <stdio.h>
#include <stdbool.h>
#include <math.h> // 包含sqrt()函数

// 检查是否为质数
bool is_prime(int num) {
    if (num <= 1)
        return false;
    if (num == 2 || num == 3)
        return true;
    if (num % 2 == 0 || num % 3 == 0)
        return false;

    for (int i = 5; i * i <= num; i += 6) { // 跳过所有6的倍数，因为它们不是质数
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}

// 质因数分解
void prime_factors(int n) {
    int count = 0; // 记录当前因子的数量
    int curr_factor = 2; // 当前正在寻找的因子

    while (n > 1) {
        if (is_prime(curr_factor)) {
            while (n % curr_factor == 0) { // 将当前因子加到每个连续因子的乘积中，直到不能整除为止
                n /= curr_factor;
                count++;
            }
            printf("%d^%d", curr_factor, count); // 输出当前质因数及其次数
            count = 0; // 重置计数器
        }
        curr_factor++; // 移动到下一个潜在的因子
    }
}

int main() {
    int num;
    printf("Enter an integer to factorize: ");
    scanf("%d", &num);

    prime_factors(num);
    printf("\n");

    return 0;
}

当运行这个程序时，用户可以输入一个整数，程序会返回该数的质因数分解。注意，这个实现并不特别高效，对于大型数字，有更好的算法如Pollard's rho算法或更复杂的数学方法可以用于质因数分解。