蓝桥杯算法提高VIP-质因数 （C语言代码）

解题思路: 短除法

参考代码:

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

int main(){
 int factor[4];
 int i = 2,j,k = 0,n;
 
 scanf("%d", &n);
 printf("%d=", n);
 while(n != 1){
  if(n%i == 0){ //n被i整除则i是n的因子
   for(j = 2; j <= sqrt(i); j++){ //判断因子i是不是质因子
    if(i%j == 0){
     break;
    }
   }
   if(j > sqrt(i)){ //j大于sqrt(i)则因子i是质因子
    factor[k] = i;
    k++;
   }
   n /= i; //改变n值
   i = 1; //回溯
  }
  i++;
 }
 printf("%d", factor[0]); //因为输出格式的问题，所以先输出factor[0]保证末尾没有多余的空格
 for(i = 1; i < k; i++){
  printf("*%d", factor[i]);
 }
 
 return 0;
}