9753번: 짝 곱

https://www.acmicpc.net/problem/9753


$O(ta\sqrt a)$ // a는 가능한 가장 큰 해

소인수분해를 한다.

#include<cstdio>
int t, x;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &x);
        for (int i = x, j, t;; i++) {
            t = i;
            for (j = 2; j*j <= t; j++) if (t%j == 0)break;
            if (j*j >= t) continue;
            t /= j;
            for (; j*j <= t; j++) if (t%j == 0) break;
            if (j*j>t) { printf("%d\n", i); break; }
        }
    }
    return 0;
}