1부터 시작하여 n까지 작은 수부터 시작한다.
만약 nxi값의 제곱근이 소수값이 아닌, 정수값이 나오면 해당 i값이 제일 작은 값이라고 생각했다. 하지만 이것은 TLE가 발생하였다.
문제에서 1 <= n <= 10 ^ 7이라고 명시하였기에 해당 범위에서 제곱근을 사용한다. 즉 1 <= n <= math.sqrt(10^7)을 한다.
왜냐하면 10^7 이하에 숫자들은 모두 math.sqrt(10^7)이하에 숫자들의 합성수로 이루어져있기 때문이다.
에라토스테네스의 체 알고리즘을 사용하여 1 <= n <= math.sqrt(10^7)의 소수를 구한다.
숫자 60을 인수분해 해보자
60 => 2 x 2 x 3 x 5로 이루어져 있는 것을 알 수 있다. 여기서 2는 2개 3은 1개 5는 1개로 이루어져 있는데 제곱수를 만들기 위해선 소수들의 개수가 짝수가 되어야 한다는 것이다. 3, 5를 짝수로 만들려면 3x5 = 15를 곱해주어야 하고 이것이 최소가 되고 정답이 된다.
이것을 코드로 나타내보면 다음과 같다.
dp = {}
n = int(input())
answer = 1
flg = False
for num in primes: ## 소수들 중
cnt = 0
if n == 1:
break
while True:
if n % num != 0: ## 해당 소수가 나누어 떨어지면 해당 소수가 몇번까지 나누어 떨어지는지 계산
if cnt % 2 != 0: ## 해당 소수의 개수가 홀수면 해당 소수 곱해준다.
answer *= num
break
n //= num
cnt += 1
if n != 1: ##만약 소수 전체를 다 해도 1이 아니라면 이것은 그 자체가 소수이기 때문에 곱해준다.
answer *= n
import math
T = int(input())
ans, primes = [], []
n = int(math.sqrt(10 ** 7))
a = [False, False] + [True for i in range(n-1)]
for i in range(2, n+1):
if a[i]:
primes.append(i)
for j in range(i*2, n+1, i):
a[j] = False
for test_case in range(1, T + 1):
dp = {}
n = int(input())
answer = 1
flg = False
for num in primes: ## 소수들 중
cnt = 0
if n == 1:
break
while True:
if n % num != 0: ## 해당 소수가 나누어 떨어지면 해당 소수가 몇번까지 나누어 떨어지는지 계산
if cnt % 2 != 0: ## 해당 소수의 개수가 홀수면 해당 소수 곱해준다.
answer *= num
break
n //= num
cnt += 1
if n != 1: ##만약 소수 전체를 다 해도 1이 아니라면 이것은 그 자체가 소수이기 때문에 곱해준다.
answer *= n
ans.append("#" + str(test_case) + " " + str(answer))
for i in ans:
print(i)