C++ program to find nth ugly number

Today, in this tutorial, we are going to see how we can get the value of the nth ugly number in C++.

Ugly numbers are the numbers which have  2,3 or 5 as their only prime factors and not any other than these. Below you can see the source code of getting nth ugly number in C++.

Number 1 is considered as an ugly number. Sequence of ugly number is 1,2,3,4,5,6,8,9,10,12,15…

Number 7,11 and 13 are excluded because they are prime numbers and 14 is excluded because 7 is the prime factor of 14.

Method to find nth ugly number 

Follow the steps::

  • Get the nth number
  • Traverse through the natural number till these many numbers aren’t found
  • To check if the number is ugly or not
    • First divide it continuously by 2 till the remainder is 0.
    • Then divide it continuously by 3 till the remainder is 0.
    • Then divide it continuously by 5 till the remainder is 0.
    • If after these, number remaining is 1 then it is an ugly number as that number does not have any other prime factor but if that number needs to be divided by some other prime factor to make it 1 then that number is not an ugly number.
  • Print the desired ugly number.

For example, checking whether 90 is ugly or not.

First dividing 90 by 2 till the remainder is 0, the output is 45.

Then dividing it continuously by 3 till the remainder is 0, the output is 5.

Then dividing it continuously by 5 till the remainder is 0, the output is 1.

Hence 90 is an ugly number.

C++ program to find nth ugly number

Now we will see the C++ program to find nth ugly number in C++. Here the number is continuously gets divided by 2,3 and 5 if the remainder is 0 till we get 1. If we get 1, the number is an ugly number else it is not.

#include <iostream>
using namespace std;

int isNumberUgly(int i)
{
  while(i%2==0)
    i=i/2;
  while(i%3==0)
    i=i/3;
  while(i%5==0)
    i=i/5;
  if(i==1)
    return 1;
  else
    return 0;
}

int nthugly(int number)
{
  int count=1;
  int no=1;

  while(number>count)
  {
    no++;
    if(isNumberUgly(no))
    {
      count++;
    }
  }
  return no;
}

int main()
{
  int n,uglyNo;
  cout << "Enter the nth ugly number to print::" << endl;
  cin>>n;
  uglyNo=nthugly(n);
  cout << n <<"th "<< "ugly number is:: "<< uglyNo << endl;
  return 0;
}

Output::

Enter the nth ugly number to print::
100
100th ugly number is:: 1536

Also, see::

Leave a Reply

Your email address will not be published. Required fields are marked *