Find the number that is not ugly number between 1 and 10,000,000

Question

I got some problem when try to finding out the not ugly number. Ugly numbers are numbers whose only prime factors are 2, 3 or 5.So what about the number not ugly number? I try to find out the not ugly numbers between 1 and 100,000,000.My program can solve the problem,but seems a little slow.How can I make it faster? Here is the code:

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
    switch(node.second)
    {
        case 2:Q.push(make_pair(node.first*2,2));
        case 3:Q.push(make_pair(node.first*3,3));
        case 5:Q.push(make_pair(node.first*5,5)); 
    }
    result[i]=node.first;
}
/*****************************************************
//Here is the approach I used:
//The initial value of the integer k is 1;
//and will increase by 1 every time 
//k will be checked if it's a ugly number,if not increase by 1,keep doing
//this till k is not a ugly number,then count how much ugly number(we may 
//call it n) is less the the
//current value of k.The result of (k-n) is the order number of this (k)　not ugly
//for example:the 1st not ugly number is 7.
// there are 6 ugly number less than 7,which are 1 2 3 4 5 6,
// k=1-->k==2-->.....k=7, k-n=7-6=1,so 7 is the 1st not ugly number
***************************************************************/
int T;  // The amount of cases
cin>>T;
while(T--)
{
    int n;
    int k=0,i=0,count=0;
    cin>>n;

    while(n)
    {
        if((k+1)==result[i]) {k++;i++;count++;}
        else 
        {
            k++;
            if(k-count==n) {cout<<k<<endl;break;}
        }
    }
}}

The big problem is that it seems not fast enough!Can you tell me how to make it faster?Or there are other method to solve the problem?

Answer 1

Generating the ugly numbers can be achieved with a recursive function.

Effectively, if N is ugly, then 2*N, 3*N and 5*N are also ugly.

Indeed, 2*N, 3*N and 5*N are ugly numbers greater than N, so you can fix a maximum value, let's say MAX and look all greater ugly numbers than N by adding also that 2*N, 3*N and 5*N (this is the recursive part).

To stop repeating searches, we can store all found numbers in a set of uglies, so when we have for example, got 6 as a product of 3*2, we don't add it (and research all its ugly descendants) when we find 2*3 (also equal to six ---we call this a collision)

The program finally gets to:

#include <cstdio>
#include <set>

using namespace std;

const unsigned N = 10000000;

set<unsigned> uglys;
unsigned n_collis = 0;


void srch_ugly(unsigned n)
{
    if (uglys.find(n) != uglys.end()) { /* found in set */
        ++n_collis;
    } else {
        uglys.insert(n);
        if (2*n < N) srch_ugly(2*n);
        if (3*n < N) srch_ugly(3*n);
        if (5*n < N) srch_ugly(5*n);
    } /* if */
} /* srch_ugly(unsigned) */

int main()
{
    unsigned col = 0; /* printing column */

    srch_ugly(1);

    /* print results */    
    printf("%lu uglys.  %u collissions.\n", uglys.size(), n_collis);
    for (set<unsigned>::iterator i = uglys.begin();
            i != uglys.end();
            ++i)
    {
        if (col >= 72) {
            puts("");
            col = 0;
        } /* if */
        col += printf("%s%i", col ? " " : "", *i);
    } /* for */
    if (col) puts("");
} /* main */

Note

Sorry for the use of printf stdio functions, but I wanted to cut lines at 72 characters and the printf functions return the number of characters printed (I don't know actually how to get the actual number of printed characters from ostream classes) so I used them instead.

Answer 2

Okay, I'll bite. Testing whether a number is ugly, by this definition, is computationally actually fairly simple. Brute-force-testing 100 million numbers with

#include <iostream>

bool is_ugly(unsigned n) {
  while(n % 5 == 0) n /= 5;
  while(n % 3 == 0) n /= 3;
  while(n % 2 == 0) n /= 2;

  return n == 1;
}

int main() {
  unsigned counter = 0;
  for(unsigned i = 1; i <= 100000000; ++i) {
    if(!is_ugly(i)) {
      ++counter;
    }
  }

  std::cout << counter << std::endl;
}

takes just over half a second in my benchmarks¹, which is quite feasible. Printing them takes a lot longer, of course, since there are 99998895 non-ugly numbers below 100000000 and your terminal has to render them all. Even redirected to /dev/null (taking the rendering out of the equation) the printing takes 6 seconds here (~10 times longer than the checking), using libstdc++ and gcc 4.9 with -O2. If you're going to generate all non-ugly numbers, this is not so easy to beat because the bottleneck is not something you can get rid of.

If, on the other hand, your goal is to generate all ugly numbers below a threshold (or to count non-ugly numbers, which comes to the same thing as counting ugly numbers and subtracting the number from the threshold) testing all non-ugly numbers along with the ugly ones is far from optimal. A better approach is to generate just the ugly numbers, since there are so few of them. This is most easily done using recursion:

#include <iostream>
#include <set>      // could also use an unordered_set, except that it turns
                    // out to be a pessimization

void generate_uglies(unsigned n, std::set<unsigned> &num, unsigned threshold) {
  // Abort recursion if we break the upper limit or find a number
  // that was already tested
  if(n <= threshold && num.find(n) == num.end()) {
    // Remember this ugly number
    num.insert(n);

    // Since n is an ugly number, these three are also ugly numbers.
    generate_uglies(n * 2, num, threshold);
    generate_uglies(n * 3, num, threshold);
    generate_uglies(n * 5, num, threshold);
  }
}

int main() {
  std::set<unsigned> num;

  generate_uglies(1, num, 100000000);

  std::cout << num.size() << std::endl;
}

This reports back, well...

$ time ./a.out 
1105

real    0m0.001s
user    0m0.000s
sys     0m0.000s

You could use this in the hope that num.find(n) == num.end() is a faster test for non-ugliness than is_ugly(n) (using the is_ugly function from before), but in my benchmarks the difference is negligible, and using a std::unordered_set is actually slower by a factor of 2-3.

Addendum: What can save some time is to generate the ugly numbers into a std::vector<bool> with 100 million elements like so:

// num is to have the wanted size in advance and be full of false
void generate_uglies(unsigned n, std::vector<bool> &num) {
  if(n < num.size() && !num[n]) {
    num[n] = true;
    generate_uglies(n * 2, num);
    generate_uglies(n * 3, num);
    generate_uglies(n * 5, num);
  }
}

and test for non-ugly numbers with !num[i] later. The !num[i] test is much faster than the is_ugly function (for values below 100 million on average by a factor of ~5)¹. This does not matter much if you're going to print them, for reasons stated above, but in different contexts it might make a noticeable difference. Note that this table requires 12.5 MB RAM.

¹ Your mileage will vary because your machine is not mine. I'm using a 1.5-year-old i7.

Answer 3

Understanding from your code, I know your really wanted is to fast to find the n-th non ugly number.

Your algorithm to find the n-th non ugly number is O(N), you can find them use binary search, it is O(log(N)).

And there are T cases, if T is very large, my method can save lots of time.

Here is my code, change from yours.

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
int main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
        switch(node.second)
        {
            case 2:Q.push(make_pair(node.first*2,2));
            case 3:Q.push(make_pair(node.first*3,3));
            case 5:Q.push(make_pair(node.first*5,5));
        }
        result[i]=node.first;
    }

    int T;  // The amount of cases
    cin>>T;
    //b_search_data[i] mean the count of non ugly number blow or equal i, i start from 1
    unsigned long b_search_data[1501];

    for (int i=0; i<1500; i++)
    {
        b_search_data[i] = result[i] - i - 1;
    }
    vector<int> search_data(b_search_data, b_search_data+1500);
    while(T--)
    {
        int n;
        int k=0,i=0,count=0;
        cin>>n;
        // use binary search here to find the n-th non ugly number instead your approach
        int position = upper_bound(search_data.begin(), search_data.end(), n-1) - search_data.begin();
        // position means
        cout<<position + n<<endl;
    }
}