当前位置：首页 > article >正文

C语言实例_12之求一正整数分解质因数

article 2024/11/28 13:11:42

1. 定义

质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。例如，对于整数(12)，它可以分解为(12 = 2\times2\times3)，这里的(2)和(3)就是(12)的质因数。因为(2)和(3)是质数，并且它们能够整除(12)。

2. 分解质因数的方法

短除法：
- 例如分解(30)的质因数。首先用最小的质数(2)去除(30)，得到(30/2 = 15)。然后再用质数(3)去除(15)，得到(15/=5)。而(5)本身就是质数。所以(30)的质因数分解式为(30 = 2 * 3 * 5)。
塔式分解法：
- 还是以(30)为例，先把(30)写成两个因数相乘的形式，比如(30 = 5 * 6)，其中(5)是质数，(6)不是。再把(6)分解为(6 = 2 * 3)，(2)和(3)都是质数。这样就得到(30)的质因数分解式为(30 = 2 * 3 * 5)。

3. 实例代码

#include <stdio.h>

// 函数用于分解质因数
void primeFactorization(int n) {
    printf("%d = ", n);

    // 从最小的质数2开始除
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            printf("%d", i);
            n /= i;
            if (n!= 1) {
                printf(" * ");
            }
        }
    }

    printf("\n");
}

int main() {
    int num;
    printf("请输入一个正整数: ");
    scanf("%d", &num);

    primeFactorization(num);

    return 0;
}

4. 解释

primeFactorization函数：
- 函数接受一个整数参数 n，用于对该整数进行质因数分解。
- 通过 printf("%d = ", n); 输出要分解的整数以及等号，为后续输出分解后的质因数做准备。
- 之后循环 for (int i = 2; i <= n; i++)，这里从最小的质数2开始，依次尝试用 i 去整除 n。
- 在循环内部，有一个 while 循环 while (n % i == 0)，只要 n 能被 i 整除，就说明 i 是 n 的一个质因数。此时执行以下操作：
······1. 通过 printf("%d", i); 输出这个质因数 i。
······2. 接着通过 n /= i; 将 n 更新为除以 i 之后的值，以便继续寻找下一个质因数。
······3. 如果更新后的 n 不等于1，说明还有其他质因数，通过 printf(" * "); 输出乘号，用于分隔不同的质因数。
······4. 当 n 最终变为1时，说明已经找到了所有的质因数，函数执行完毕。