def check(x):
cnt = 0; sq = 0
q = [(1,-1,1)]
while q:
n,i,s = q.pop()
for j in range(i+1,P):
n1 = n*prime[j]**2
if n1>x:
break
cnt += x//n1*s
sq |= int(not x%n1)
q.append((n1,j,-s))
return cnt,sq
prime = []; visited = [0]*200001
for i in range(2,200001):
if not visited[i]:
prime.append(i)
if i<448:
for j in range(1,200000//i+1):
visited[i*j] = 1
P = len(prime)
K = int(input())
x,c = 1<<34,33
while 1:
k,sq = check(x)
if k<K:
x += 1<<c
elif k>K or k==K and not sq:
x -= 1<<c
else:
break
c -= 1
print(x)
= [백준 1557번] 제곱 ㄴㄴ (Python3) (tistory.com)
숫자의 범위가 약간 달라지고(따라서 소수의 범위도 바꿔야한다), K번째 제곱ㄴㄴ수가 아니라 K번째 제곱ㄴㄴ"아닌" 수를 출력해야한다는 것만 다르다.
이외 풀이는 똑같다.