d085: 根號運算

內容 ：
    根號運算
    輸入很多, 請用 EOF
    輸入 3 則為 √3
    輸入 4 則為 2
    數入 12 則為 2√3
    有負數喔
    請弄好 "i"

輸入說明 ：
    一堆數字,行行排列

輸出說明 ：
    一堆數字,行行排列
    注意
    √ 要用成 _/

範例輸入 ：
3
4
12
-3
-4
-12

範例輸出 ：
_/3
2
2_/3
_/3i
2i
2_/3i

提示 ：
    聰明的人會加速
    拜託好不好
    暴力會TLE

程式碼 ：

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

int main()
{
    int a,i,minus,sqr,left;
    
    while(scanf("%d",&a)==1)
    {
        if(a == 0)
        {
            printf("0\n");
            continue;
        }
        minus = 0;
        if(a < 0)
        {
            minus = 1;
            a = -a;
        }
        
        sqr = sqrt(a);
        left = 1;
        for(i=2; i<=sqr; i++)
        {
            while(a%(i*i) == 0)
            {
                left *= i;
                a /= (i*i);
            }
        }
                        
        if(left != 1)
            printf("%d",left);
        
        if(a != 1)
            printf("_/%d",a);
        
        if(minus)
            printf("i");
        printf("\n");
    }
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=d085