title: nᵗʰ ugly number
body: <p>Numbers whose only prime factors are 2, 3, or 5 are called <strong>ugly numbers</strong>.</p>
  <p>Example:</p>
  <pre><code>1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 
  </code></pre>
  <p>1 can be considered as 2^0.</p>
  <p>I am working on finding n<sup>th</sup> ugly number. Note that these numbers are extremely sparsely distributed as <code>n</code> gets large.</p>
  <p>I wrote a trivial program that computes if a given number is ugly or not. For <code>n &gt; 500</code> - it became super slow. I tried using memoization - observation: <code>ugly_number * 2</code>, <code>ugly_number * 3</code>, <code>ugly_number * 5</code> 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?</p>
  <p>Using a concept similar to <em>Sieve of Eratosthenes</em> (thanks Anon)</p>
  <pre><code>    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;
      }
  </code></pre>
  <p><code>i</code> is the n<sup>th</sup> ugly number.</p>
  <p>Even this is pretty slow. I am trying to find the 1500<sup>th</sup> ugly number.</p>