1329. Numbers Built Only From 2, 3 and 5
A number is SMOOTH here when its only prime factors are 2, 3 and 5. The sequence begins:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, ...
1 counts, having no prime factors at all. 7 does not, and neither does 14.
Print the nth smooth number, counting from 1.
Testing each integer in turn and factorising it wastes almost all its work: the 1500th smooth number is over 800 million, so nearly every candidate fails.
Build the sequence instead. Every smooth number after 1 is some earlier smooth number times 2, 3 or 5. So keep the list built so far and three positions into it, one per multiplier. The next value is the smallest of the three candidates, and only the positions that produced it advance.
That last word matters. When two candidates tie, as at 6 which is both 2 times 3 and 3 times 2, BOTH positions must advance. Advancing only one leaves a duplicate in the list and every later answer is shifted.
Constraints - `1 ≤ n ≤ 1500`
Input
One line containing the integer n.
Output
Print the nth smooth number.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.