Ugly Number e.g. Numer Whose prime Factor are 2 or 3 or

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.
Write a program to find and print the 150′th ugly number.

1st Method

using namespace std;
#define MAXSIZE 15
 
int minimum(int x,int y,int z)
{
    if (x      return (y}
 
int nextUgly(int nth)//nth
{
    int num2,num3,num5;
    int ugly[MAXSIZE], ptr2, ptr3, ptr5;
        ugly[0]=1;int i=0;
        ptr2=ptr3=ptr5=0;
 
   for(i=1;i  {
    num2=ugly[ptr2]*2;
    num3=ugly[ptr3]*3;
    num5=ugly[ptr5]*5;
 
    ugly[i]=minimum(num2,num3,num5);
 
    if(ugly[i]==num2) ptr2++;
    if(ugly[i]==num3) ptr3++;
    if(ugly[i]==num5) ptr5++;
 
   }
 
    return ugly[nth-1];
}
 
int main()
{
 
    printf("15th Ugly number is %d\n",nextUgly(15));
}


TC O(n)
SC O(1)

2nd Method

Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.

To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.

For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.


# include
# include

/*This function divides a by greatest divisible
power of b*/
int maxDivide(int a, int b)
{
while (a%b == 0)
a = a/b;
return a;
}

/* Function to check if a number is ugly or not */
int isUgly(int no)
{
no = maxDivide(no, 2);
no = maxDivide(no, 3);
no = maxDivide(no, 5);

return (no == 1)? 1 : 0;
}

/* Function to get the nth ugly number*/
int getNthUglyNo(int n)
{
int i = 1;
int count = 1; /* ugly number count */

/*Check for all integers untill ugly count
becomes n*/
while (n > count)
{
i++;
if (isUgly(i))
count++;
}
return i;
}

/* Driver program to test above functions */
int main()
{
unsigned no = getNthUglyNo(150);
printf("150th ugly no. is %d ", no);
getchar();
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/zyBWV