title: Given X, determine n, where X is n-th ugly number
body: <blockquote>
    <p>"Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The
    sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly
    numbers. By convention, 1 is included."</p>
  </blockquote>
  
  <p>Given number X, determine the order of X in that sequence.
  Example : X = 12, output : 10.</p>
  
  <p>I made a brute force algorithm, which runs in O(XlogX):</p>
  
  <pre><code>long long cnt = 0;
  for(long long i = 1; i&lt;X; i++)
  {
    long long tmp = i;
    while(tmp % 2 == 0) tmp/=2;
    while(tmp % 3 == 0) tmp/=3;
    while(tmp % 5 == 0) tmp/=5;
    if(tmp == 1) cnt ++;
  }
  cout &lt;&lt; cnt+1 &lt;&lt; endl;
  </code></pre>
  
  <p>However, X might be 1e18 and there might be 10^5 queries, each query gives us a number X.</p>
  
  <p>Does anyone know a more efficient algorithm to perform this operation? Thank you.</p>