题解 | #质数因子#

#include <stdio.h>

int main() {

    //原理：
    //①质数（Prime Number）：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫作质数
    //②任何大于1的正整数都可以被拆分成多个质数相乘。
    //③一个数字n可以拆分成a*b，那么 a 或 b 至少有一个小于 根号n
    //1 1*1     1是没有质数因子的，题目有问题
    //2 1*2     2的质数因子是2
    //3 1*3
    //4 2*2
    //5 1*5
    //6 2*3
    //15 3*5
    //180 2*2*3*3*5
    //...

    unsigned int num = 0;
    scanf("%u", &num);

    //以下方发超时
    // unsigned int i =0;
    // for (i = 2; i <= num; i++) {
    //     if (num%i == 0) { //能被i取余，说明能够被i整除
    //         while(num%i == 0) {
    //             //把所有 i的因子的数字都取出，
    //             //例如：i=2; 要把是2的因子都去掉；这样i=4是，num就整除不了了
    //             printf("%u ", i);
    //             num /= i;
    //         }
    //     }
    // }

    unsigned int i = 0;
    for (i = 2; i*i <= num; i++) {//一个数字n可以拆分成a*b，那么 a 或 b 至少有一个小于 根号n
        if (num % i == 0) { //能被i取余，说明能够被i整除
            while (num % i == 0) {
                //把所有 i的因子的数字都取出，
                //例如：i=2; 要把是2的因子都去掉；这样i=4是，num就整除不了了
                printf("%u ", i);
                num /= i;
            }
        }
    }

    if (num !=1) { //num != 1说明没被除尽，还有一个大于 根号n 的因子，即是num
        printf("%u", num);
    }
    return 0;
}

收获点：

做不出来的原因是数学知数不过关，原理：

①质数（Prime Number）：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫作质数

②任何大于1的正整数都可以被拆分成多个质数相乘。

③一个数字n可以拆分成a*b，那么 a 或 b 至少有一个小于 根号n