You can pre-calculate calculate the answer by checking all the numbers till you find the 1500'th ugly number by checking each number prim factors to see whether they are just 2, 3 and 5.

OR

You can build a list of ugly numbers in a bottom-up dynamic programming approach. How?

I use a set and a vector of integers for simplicity. Both the set and the vector have the same numbers, I can use just a set too without no vectors.

I must build the list of ugly numbers, since my first ugly number in the list is 1, so the next one must be retrieved by multiplying 2, 3 and 5 by 1 ( the first number in the list ). I pick 2*1 ( the minimum ), then 2 must be multiplied by the next number in the list( 2 ). At next step I choose 3 out of ( 2*2, 3*1, 5*1 ), and 3 must be multiplied by 2( the next number in the list for factor 3 ), then I pick 4 out of ( 2*2, 3*2, 5*1 ) and so on.

2*1 3*1 5*1

2*2 3*2 5*2

2*3 3*3 5*3

2*4 3*4

2*5

2*6

My function min3 is invoked in this order:

2*1, 3*1, 5*1

2*2, 3*1, 5*1

2*2, 3*2, 5*1

2*3, 3*2, 5*1

2*3, 3*2, 5*2

2*4, 3*2, 5*2

2*4, 3*3, 5*2

2*5, 3*3, 5*2

2*5, 3*4, 5*2

2*6, 3*4, 5*2

2*6, 3*4, 5*3

2*8, 3*4, 5*3

2*8, 3*5, 5*3

........

........