Question: Ugly numbers are numbers whose only prime factors are 2, 3 or 5. First 10 ugly numbers are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

By convention, 1 is included. Write a program to find and print the first 1000 ugly numbers.

Answer: Consider an array of first 10 ugly numbers: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, , , , }

Next ugly number can be calculated by just multiplying one of all these numbers with 2 or 3 or 5.

The least number whose double is not present in the list is 8 (any number before this has its double present in the list). So one of the candidates for next ugly number is 8*2=16

The least number whose multiple by 3 is not present in the list is 5 (any number before this has its multiplied by 3 present in the list). So other candidate for next ugly number is 5*3 = 15.

The least number whose multiple by 5 is not present in the list is 3 (any number before this has its multiplied by 5 present in the list). So other candidate for next ugly number is 3*5 = 15.

Least of these three numbers (15) is our next ugly number.

Now how to choose next ugly number is pretty simple. Since our ugly number is 15 it means now 3*5 and 5*3 are present in the list. So next numbers whose multiple by 3 and 5 respectively are not present in the list are 6 and 4 respectively. The least number whose double is not present in the list remains unchanged at 8. So next candidates are 8*2, 6*3 and 4*5. We will continue in this manner for further list.

Algorithm: Keep 3 pointers with you and keep track whose multiple by 2,3 and 5 are present and whose are not. Choose the least number of next candidates and increase the pointer by 1 for the chosen one. If 2 candidates are same, and we chose that number, increment both the pointers as in example above.

Code: 

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 1000

int ugly[MAXSIZE], ptr2, ptr3, ptr5;

int minimum(int x,int y,int z)
{
   if (x<y) return (x<z?x:z);
     return (y<z?y:z);
}

int nextUgly(int num)
{
   int num2,num3,num5;
   if(num==0)
   {
       ugly[num]=1;
       ptr2=ptr3=ptr5=0;
       return  ugly[num];
   }

   num2=ugly[ptr2]*2;
   num3=ugly[ptr3]*3;
   num5=ugly[ptr5]*5;

   ugly[num]=minimum(num2,num3,num5);

   if(ugly[num]==num2) ptr2++;
   if(ugly[num]==num3) ptr3++;
   if(ugly[num]==num5) ptr5++;

   return ugly[num];
}

int main()
{
   int i;
   for(i=0; i<MAXSIZE; i++)
       printf("Ugly number no. %d is %d\n", i+1,nextUgly(i));
}


Code explanation:
ptr2 in this program is just to keep the index of least number whose multiple of 2 is not present in the list.

ptr3 in this program is just to keep the index of least number whose multiplied by 3 is not present in the list.

ptr5 in this program is just to keep the index of least number whose multiplied by 5 is not present in the list.

In our example, ptr2 is pointing to 8, ptr3 is pointing to 5 and ptr5 is pointing to 3.
Every time we decide your next ugly number ptr2, ptr3 and ptr5 are moved to next location accordingly.

As in this case our next ugly number is 15 hence both ptr3 and ptr5 will be incremented by one. Now they will point to 6 and 4 respectively.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.