Placeholder

#1318

못생긴 수 1초 256MB

문제

못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.

 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

 

이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 nn이 주어졌을 때, nn번째 못생긴 수를 출력하는 프로그램을 작성하라.


입력

한 줄에 양의 정수 nn (n≤1,500n≤1,500)이 주어진다.

  • 입력에 00 이 주어질 때까지 계속한다.

  • 입력은 최대 100,000100,000번까지만 주어짐이 보장된다.


출력

출력에는 nn번째 못생긴 수를 출력한다.


예제1

입력
1 

2 

9 

0
출력
1 

2

10

출처

New Zealand 1990 Division I,UVA 136 Ugly Numbers, poj 1338


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.