[백준 8464번] Non-Squarefree Numbers (Python)

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번째 제곱ㄴㄴ"아닌" 수를 출력해야한다는 것만 다르다.

이외 풀이는 똑같다.