제곱 인수를 가진 수

시간 제한2초메모리 제한32 MB

요약

n이 10^10까지 주어질 때, 1보다 큰 d에 대해 d^2로 나누어지는 양의 정수 중 n번째 수를 구한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

양의 정수 $k$ 가 $d > 1$ 인 모든 정수 $d$ 에 대해 $d^2$ 으로 나누어떨어지지 않을 때, $k$ 를 제곱 인수가 없는 수(squarefree)라고 합니다. 반대로 $d > 1$ 인 어떤 정수 $d$ 가 존재하여 $k$ 가 $d^2$ 으로 나누어떨어지면, $k$ 를 제곱 인수를 가진 수(non-squarefree)라고 합니다.

예를 들어 제곱 인수를 가진 수를 작은 것부터 나열하면 $4, 8, 9, 12, 16, \dots$ 입니다.

제곱 인수를 가진 수를 오름차순으로 나열했을 때 $n$ 번째 수를 출력하세요.

입력

첫째 줄에 정수 $n$ 이 주어집니다. ( $1 \le n \le 10^{10}$ )

출력

$n$ 번째 제곱 인수를 가진 수를 한 줄에 출력하세요.

예제1

예제 1
입력
```
10
```
예상 출력
```
27
```