C语言中因子分解的常见方法

在C语言中，因子分解是将一个数分解为若干个质数的乘积

1. 试除法：从2开始，逐个尝试将给定数字除以每个整数，直到找到一个能够整除该数字的因子。然后将原数字除以该因子，并继续寻找下一个因子，直到无法找到更多因子为止。

#include<stdio.h>

void factorize(int num) {
    int i;
    printf("Factors of %d: ", num);
    for (i = 2; i <= num; i++) {
        while (num % i == 0) {
            printf("%d ", i);
            num /= i;
        }
    }
    printf("\n");
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    factorize(num);
    return 0;
}

2. 质因数分解法：类似于试除法，但在寻找因子时只考虑质数。这种方法通常比试除法更高效，因为质数的数量相对较少。

#include<stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void factorize(int num) {
    int i;
    printf("Factors of %d: ", num);
    for (i = 2; i <= num; i++) {
        while (is_prime(i) && num % i == 0) {
            printf("%d ", i);
            num /= i;
        }
    }
    printf("\n");
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    factorize(num);
    return 0;
}

这两种方法都可以用来实现因子分解。试除法适用于较小的数字，而质因数分解法适用于较大的数字。在实际应用中，可以根据需要选择合适的方法。