10965. 제곱수 만들기

10965. 제곱수 만들기

풀이(처음 풀이 - TLE)

1부터 시작하여 n까지 작은 수부터 시작한다.
만약 nxi값의 제곱근이 소수값이 아닌, 정수값이 나오면 해당 i값이 제일 작은 값이라고 생각했다. 하지만 이것은 TLE가 발생하였다.

풀이(에라토스테네스의 체)

1. 문제에서 1 <= n <= 10 ^ 7이라고 명시하였기에 해당 범위에서 제곱근을 사용한다. 즉 1 <= n <= math.sqrt(10^7)을 한다.
   왜냐하면 10^7 이하에 숫자들은 모두 math.sqrt(10^7)이하에 숫자들의 합성수로 이루어져있기 때문이다.
   

2. 에라토스테네스의 체 알고리즘을 사용하여 1 <= n <= math.sqrt(10^7)의 소수를 구한다.
   

3. 숫자 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)