求救！为什么一直TLE！新手自闭了

新手上路，真的不知道为什么总是TLE，简直比WA还绝望，求助

int main()
{   int a,b,c,d,i,j;
    scanf("%d",&a);
    for(b=0;b<a;b++)
    { scanf("%d%d",&c,&d);
    for(i=d+1;i>1;i--)
    {
        if((c%i==0)&&(d%i==0))
            break;
    }
        for(j=d;j<c*d;j++)
    {
        if((j%c==0)&&(j%d==0))
           break;
    }
        printf("%d %d\n",i,j);
    }
    return 0;
}

算法太暴力了，优化一下。
比如你的最小公倍数求法：之前已经求除最小公约数了，可以用C,D中较小的数除以最小公约数再乘以较大的数，这样直接得出结果。
同理，最小公倍数也有相应算法，比如辗转相除法等等

望采纳