求一个数的质数分解 C语言

在C语言中，求一个数的质数分解通常涉及到遍历该数的所有可能的质数因子，直到找到可以整除的因子为止。以下是一个简单的示例，展示了如何编写这样的功能：

#include <stdio.h>
#include <stdbool.h> // 使用bool类型

bool is_prime(int num) {
    if (num <= 1) return false; // 0和1不是质数
    for (int i = 2; i * i <= num; i++) { // 只需检查到 sqrt(num)
        if (num % i == 0) return false;
    }
    return true;
}

void prime_factors(int n, int factors[]) {
    int count = 0;
    for (int i = 2; ; i++) { // 从2开始尝试质数因子
        if (is_prime(i) && n % i == 0) {
            factors[count++] = i; // 找到因子，增加计数并保存
            n /= i; // 更新n
        }
        if (n == 1 || !is_prime(i)) break; // 如果n变为1或不是质数，退出循环
    }
    factors[count] = n; // 如果n仍有余数，则n就是最后一个质因子
}

int main() {
    int input;
    printf("Enter a number to factorize: ");
    scanf("%d", &input);

    int factors[Maxsize]; // 定义一个数组来存放质因数
    int actual_count = prime_factors(input, factors);

    printf("Prime factors of %d are: ", input);
    for (int i = 0; i < actual_count; i++) {
        printf("%d ", factors[i]);
    }

    return 0;
}

在这个例子中，`prime_factors` 函数接收一个整数 `n` 和一个预分配的数组 `factors`，它会找出并存储所有质因数。`is_prime` 函数则用于判断一个数是否为质数。注意，在主函数中，我们先读取用户输入的数字，然后计算质因数并打印出来。