C语言时间超限问题

题目：已知正整数n，求最小的正整数x，使得n*x是一个平方数。例如n=12，则最小的x是3，n*x为36是一个平方数。
输入一个正整数n,n<2^31;
要求输出最小正整数x;
这是我的代码：
#include<stdio.h>
#include<math.h>
int main(void)
{
    long long n,x,s,t;
    scanf("%ld",&n);
    for(x=1;x<=n;x++){
        s=x*n;
        t=(int)(sqrt(s));
        if(t*t==s){
            printf("%ld",x);
            break;
        }
    }
    return 0;
}
但是时间超限，我不知道要怎么改