质因数分解不超时间求解

Question

题目：质因数分解

代码：
#include<stdio.h>
#include<math.h>
int main ()
{ long long a,i,k;
int j=1;
while(1){
scanf("%I64d",&a);
k=sqrt(a);
for(i=2;i<=k;i++){
if(a%i==0){
printf("%I64d",i);
a/=i;
while(a%i==0){
while(a%i==0){
a/=i;
j++;
}
printf("^%d",j);
}
if(a%i!=0&&a!=1){
printf("*");
}
}
j=1;
}
if(a!=1)
{
printf("%I64d",a);
}
printf("\n");
}
}
疑问：超时了，求改进

Answer 1

#include <stdio.h>
int main()
{
    //利用count统计阶乘次数
    int n,i,count;
    while(scanf("%d",&n)){

        for(i=2; i*i<=n; i++)
    {
        //如果输入的数为素数则会直接输出
        if(n%i!=0)
            continue;
        count=0;
        do{
            count++;
            //n反复除以因子i
            n=n/i;
        }while(n%i==0);

        printf("%d",i);
        if(count>1)
            printf("^%d",count);
        if(n>1)
            printf("*");
    }
    if(n>1)
        printf("%d",n);
    printf("\n");
    }


}