题解 | 分解质因数

#include <stdio.h>
#include <math.h>
int prim(long long n){//判断是不是素数/质数的函数
    if(n==1) return 0;// 1不是 素数/质数
    if(n==2) return 1;// 2 是素数
    for(int i =2;i<=sqrt(n);i++){//素数2到根号n 如果比根号n大 则必有能被整除的数 为根号n
        if(n%i==0) return 0;//能被整除 不是素数
    }
    return 1;//循环结束 没有能被整除的数 是素数
}
int main() {
    long long n;
    scanf("%lld",&n);
    int i;
    for(i =2;i<n/2;i++){//数学定律：一个数n 除了它本身 它的因子都在 1~n/2之间
        if(prim(i)==1 && n%i==0){//判断是不是素数且是不是 因子
             n=n/i;//判断结束后 n/i 这样就不会漏掉其他的因子
             printf("%d ",i);//输出因子
             i=1;//让i=1  循环重新开始判断 这时候寻找的是n/i(第一次)的质因数
        }
    }//循环结束后n/i(数次)，此时的n 也是原来数n的质因数
  printf("%d",n);
    return 0;
}