[C++知识库]递归实现因式分解（c语言）

一、分析

1、因数输出的条件

• 能够被num整除
• 是质数?

2、除数是否可被num整除

• 若可整除，除数是否为素数？是则输出除数，否则继续因式分解
• 若不可整除，除数+1

3、除数边界

• 除数初始为2，直到除数>sqrt(num)，程序结束

二、代码

• 1、导入模块

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

• 2、判断数字是否为素数

bool IsPrimeNum(int num) {
    // num是否为素数
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

• 3、因式分解

void Disolve(int num) {    
    // 因式分解
    int i = 2;

    while (i <= sqrt(num)) {
        if (num % i == 0) {
            if (IsPrimeNum(i)) {
                printf("* %d ", i);
            } else {
                Disolve(i);
            }
            num /= i;
        } else {
            i++;
        }
    }

}



int main() {
    int num = 200;
    printf("%d = 1 ", num);

    Disolve(num);

    return 0;
}