C语言如何分解正整数为质因数？

C语言实现正整数分解质因数

以下是一个用C语言实现将正整数分解质因数的程序：

#include <stdio.h>
void primeFactorization(int num) {
    // 处理2的因子
    while (num % 2 == 0) {
        printf("2 ");
        num = num / 2;
    }
    // 处理奇数因子，从3开始，每次加2
    for (int i = 3; i <= num; i = i + 2) {
        // 当i*i <= num时继续循环
        while (num % i == 0) {
            printf("%d ", i);
            num = num / i;
        }
    }
    printf("\n");
}
int main() {
    int number;
    printf("请输入一个正整数: ");
    scanf("%d", &number);
    if (number <= 1) {
        printf("请输入大于1的正整数，\n");
        return 1;
    }
    printf("%d的质因数分解为: ", number);
    primeFactorization(number);
    return 0;
}

程序说明

1. 函数primeFactorization:

   • 首先处理所有2的因子（偶数情况）
   • 然后从3开始，每次检查递增的奇数（3,5,7,...）
   • 对于每个数i，检查是否能整除当前num，如果能则输出i并更新num
   • 循环直到num变为1

2. 主函数main:

   • 获取用户输入的正整数
   • 检查输入是否有效（大于1）
   • 调用质因数分解函数并输出结果

示例运行

请输入一个正整数: 60
60的质因数分解为: 2 2 3 5 

请输入一个正整数: 17
17的质因数分解为: 17 

请输入一个正整数: 100
100的质因数分解为: 2 2 5 5 

这个程序可以高效地分解任何正整数的质因数。