#include <stdio.h>

int main(void)
{
int number;
while(scanf("%[2-1000000]", number)!=EOF) //輸入數字
{
for(int i=2; i<=number; i++)
{
int a=0;
if(number%i==0) // 如果number能被i整除
{
while(number%i==0) //能被i整除a次
{
number/=i;
a++;
}

if(a>1&&number!=1) // number!=1表還可能被除
printf("%d^%d * ", i, a);
if(a==1&&number!=1)
printf("%d * ", number);
if(a>1&&number==1) //number==1表最後一次，故無*
{
printf("%d^%d", i, a);
break;
}
if(a==1&&number==1)
{
printf("%d", i);
break;
}
}
}
printf("\n");
}
return 0;
}

有兩個方向可以改善

每次要計算時作為底數的質數應該都是一樣的，所以請先把1000000以內的先紀錄

再來要判斷 x 是不是質數，只要判斷 sqrt(x)以內的質數即可

第一點結合第二點的性質可以發現其實你只要存 sqrt(1000000)=1000以內的質數即可

如果 x 無法被1000以內的質數整除就代表他是在1000000以內的質數