C 语言实例 – 求一个整数的所有因数（保姆级教程）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

在编程学习的旅程中，理解基础算法和数学逻辑是提升技能的关键一步。本文以“C 语言实例 – 求一个整数的所有因数”为主题，通过循序渐进的方式，帮助编程初学者和中级开发者掌握这一经典问题的解决方法。因数分解是数学与编程结合的典型场景，不仅能巩固对循环结构和条件判断的理解，还能培养算法优化的思维习惯。

在数学中，因数是指能够整除给定整数且不产生余数的整数。例如，6 的因数包括 1、2、3、6。在编程中，求一个数的所有因数需要通过算法遍历可能的候选值，并筛选出符合条件的数值。

因数的特性与规律

1. 对称性：若 a 是 n 的因数，则 n/a 也是 n 的因数。例如，当 a=2 时，n=6 的对应因数是 6/2=3。
2. 范围限制：因数的搜索范围不需要遍历到 n，只需到 √n 即可。例如，当 n=100 时，遍历到 10 就能覆盖所有因数对。
3. 正负性：因数可以是正数或负数，但通常问题默认讨论正因数。

第一步：明确需求与边界条件

在编写代码前，需明确以下问题：

• 输入的整数是否为正整数？若为负数或零，如何处理？
• 是否需要输出重复的因数？（因数本身不会重复，但需注意对称性导致的重复存储）
• 输出格式如何？是否需要排序？

边界条件示例

第二步：设计算法逻辑

基础版本：遍历 1 到 n

最直观的方法是遍历从 1 到 n 的所有整数，判断是否能整除 n。例如：

#include <stdio.h>  

void print_factors(int n) {  
    printf("因数列表：");  
    for (int i = 1; i <= n; i++) {  
        if (n % i == 0) {  
            printf("%d ", i);  
        }  
    }  
    printf("\n");  
}  

缺点：当 n 很大时（如 n=1000000），算法效率低下，时间复杂度为 O(n)。

优化版本：利用对称性减少遍历范围

通过数学规律，只需遍历到 √n，并同时记录因数对。例如：

#include <stdio.h>  
#include <math.h>  

void print_factors(int n) {  
    printf("因数列表：");  
    int sqrt_n = sqrt(n);  
    for (int i = 1; i <= sqrt_n; i++) {  
        if (n % i == 0) {  
            printf("%d ", i);  
            if (i != n / i) { // 避免平方数重复输出  
                printf("%d ", n / i);  
            }  
        }  
    }  
    printf("\n");  
}  

优势：时间复杂度降低至 O(√n)，例如 n=100 时，仅需遍历到 10。

步骤 1：输入与验证

首先，程序需要从用户输入中获取整数，并验证其是否为正整数。

#include <stdio.h>  

int get_positive_integer() {  
    int n;  
    printf("请输入一个正整数：");  
    scanf("%d", &n);  
    while (n <= 0) {  
        printf("输入无效，请重新输入一个正整数：");  
        scanf("%d", &n);  
    }  
    return n;  
}  

关键点：通过循环确保输入合法性，避免后续计算出错。

步骤 2：因数收集与排序

在优化版本中，因数可能被分散输出。若需按升序排列，可先将结果存储在数组中，再排序。

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  

void collect_factors(int n, int** factors, int* size) {  
    int sqrt_n = sqrt(n);  
    *size = 0;  
    for (int i = 1; i <= sqrt_n; i++) {  
        if (n % i == 0) {  
            if (i != n/i) {  
                (*factors)[(*size)++] = i;  
                (*factors)[(*size)++] = n/i;  
            } else {  
                (*factors)[(*size)++] = i;  
            }  
        }  
    }  
}  

void sort_factors(int* factors, int size) {  
    for (int i = 0; i < size; i++) {  
        for (int j = i + 1; j < size; j++) {  
            if (factors[i] > factors[j]) {  
                int temp = factors[i];  
                factors[i] = factors[j];  
                factors[j] = temp;  
            }  
        }  
    }  
}  

int main() {  
    int n = get_positive_integer();  
    int size = 0;  
    int capacity = 20; // 初始容量，可动态扩容  
    int* factors = (int*)malloc(capacity * sizeof(int));  
    collect_factors(n, &factors, &size);  
    sort_factors(factors, size);  
    printf("有序因数列表：");  
    for (int i = 0; i < size; i++) {  
        printf("%d ", factors[i]);  
    }  
    free(factors);  
    return 0;  
}  

关键点：

1. 动态分配内存以适应不同因数数量。
2. 排序确保输出结果有序。

优化点 1：避免重复存储

在对称性遍历中，需注意 i 和 n/i 是否相等，例如当 n 是平方数（如 25）时，5 仅需存储一次。

优化点 2：提前终止条件

在遍历过程中，若发现 i 超过 √n，可立即跳出循环。

扩展案例：求最大公约数（GCD）

因数分解可延伸到其他数学问题。例如，通过枚举因数求 GCD：

int gcd(int a, int b) {  
    int min = (a < b) ? a : b;  
    for (int i = min; i >= 1; i--) {  
        if (a % i == 0 && b % i == 0) {  
            return i;  
        }  
    }  
    return 1; // 理论上不会出现  
}  

问题 1：输出重复因数

原因：未处理 i 和 n/i 相等的情况。
解决方案：在存储时增加条件判断。

问题 2：未覆盖所有因数

原因：遍历范围未正确计算 √n。
解决方案：使用 sqrt() 函数并向下取整。

通过本文的讲解，读者应能掌握以下核心能力：

1. 理解因数的数学定义与算法逻辑。
2. 编写基础与优化版本的因数求解程序。
3. 处理输入验证、动态内存分配等进阶问题。

“C 语言实例 – 求一个整数的所有因数”不仅是算法练习的基础，更是理解数学与编程结合的重要案例。通过逐步优化代码，读者可以培养系统化思考和代码调试的能力，为后续学习更复杂的算法（如质因数分解、RSA 加密等）奠定基础。

希望本文能成为您编程学习路上的实用指南！