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

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

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

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

程序说明

1. 输入处理：

   • 程序首先提示用户输入一个正整数
   • 检查输入是否大于1，因为1没有质因数

2. 分解算法：

   • 首先处理所有2的因数（偶数情况）
   • 然后从3开始，每次递增2（只检查奇数）
   • 对于每个数，持续除以它直到不能再除为止

3. 输出：

   程序会按顺序输出所有质因数

   
   （图片来源网络，侵删）

示例运行

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

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

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

这个算法的时间复杂度是O(√n)，对于大数来说效率可能不高,但对于一般大小的正整数已经足够。