nth ugly number
- by Anil Katti
Numbers whose only prime factors are 2, 3 or 5 are called ugly numbers.
Example:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
1 can be considered as 2^0.
I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.
I wrote a trivial program that computes if a given number is ugly or not. For n 500 - it became super slow. I tried using memoization - observation: ugly_number * 2, ugly_number * 3, ugly_number * 5 are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?
Using a concept similar to "Sieve of Eratosthenes" (thanks Anon)
for (int i(2), uglyCount(0); ; i++) {
if (i % 2 == 0)
continue;
if (i % 3 == 0)
continue;
if (i % 5 == 0)
continue;
uglyCount++;
if (uglyCount == n - 1)
break;
}
i is the nth ugly number.
Even this is pretty slow. I am trying to find 1500th ugly number.
