Display N Ugly Numbers

In number theory, an "Ugly Number" is defined as a positive integer whose only prime factors are 2, 3, or 5. In other words, a number is considered ugly if it can be expressed as a product of powers of 2, 3, and 5. The first few ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, and so on.

Problem Statement

The task is to display the first N ugly numbers. Given an integer N, we need to find and print the first N ugly numbers in ascending order.

Example

Let's say N = 10. We need to find the first 10 ugly numbers.

The first 10 ugly numbers are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12

Pseudocode

Function factor(number, checker):
    while number % checker == 0:
        number = number / checker
    return number

Function is_ugly(number):
    number = factor(number, 2)
    number = factor(number, 3)
    number = factor(number, 5)
    if number == 1:
        return 1
    else:
        return 0

Function display_ugly(size):
    i = 1
    while size > 0:
        if is_ugly(i) == 1:
            print i
            size = size - 1
        i = i + 1

Function main():
    n = 20
    display_ugly(n)

main()

To solve this problem, we can use a function to check if a given number is ugly or not. We'll start from 1 and keep incrementing the number until we find N ugly numbers. For each number, we'll check if it is ugly using the is_ugly function. If it is ugly, we'll print it, and once we have printed N ugly numbers, we'll stop.

Algorithm

1. Define a function is_ugly(number) that takes an integer as input and returns 1 if it is an ugly number, and 0 otherwise.
2. Within the is_ugly function:
   • Repeatedly divide the number by 2, 3, and 5 as long as it is divisible by these numbers.
   • Finally, check if the remaining number is 1. If yes, return 1 (ugly number), else return 0.
3. In the display_ugly(size) function:
   • Start from i = 1.
   • Check if i is an ugly number using the is_ugly function.
   • If it is an ugly number, print it and decrement size by 1.
   • Repeat steps 2 and 3 until size becomes 0.
4. In the main() function:
   • Define the value of N (e.g., n = 10) for the number of ugly numbers to be displayed.
   • Call the display_ugly(n) function to display the first N ugly numbers.

Code Solution

• C
• Cpp
• Java
• Python
• Node Js
• Php
• C#
• Ruby
• Swift

//C Program
//Display N Ugly Numbers
#include <stdio.h>

int factor(int number,int checker)
{
  while(number%checker==0)
  {
    number/=checker;
  }
  return number;
}
int is_ugly(int number)
{
  number=factor(number,2);
  number=factor(number,3);
  number=factor(number,5);
  return number;
}
void display_ugly(int size)
{
  
  for (int i = 1; size > 0; ++i)
  {
    if(is_ugly(i)==1)
    {
      printf("%d\n",i );
      size--;
    }
  }
}

int main()
{

  int n = 20;
  
  display_ugly(n);

  return 0;
}

1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
32
36

/*
  C++ Program
  Display N Ugly Numbers
*/
#include <iostream>

using namespace std;

class Number {
public:
  int factor(int number, int checker) {
    while (number % checker == 0) {
      number /= checker;
    }
    return number;
  }
  int is_ugly(int number) {
    number = this->factor(number, 2);
    number = this->factor(number, 3);
    number = this->factor(number, 5);
    return number;
  }
  int display_ugly(int size) {
    for (int i = 1; size > 0; ++i) {
      if (this->is_ugly(i) == 1) {
        cout << " " << i;
        size--;
      }
    }
  }

};

int main() {
  Number obj;
  int n = 20;
  obj.display_ugly(n);
}

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

/*
  Java Program
  Display N Ugly Numbers
*/
public class Number {

  public int factor(int number, int checker) {
    while (number % checker == 0) {
      number /= checker;
    }
    return number;
  }
  int is_ugly(int number) {
    number = factor(number, 2);
    number = factor(number, 3);
    number = factor(number, 5);
    return number;
  }
  public void display_ugly(int size) {

    for (int i = 1; size > 0; ++i) {
      if (is_ugly(i) == 1) {
        System.out.println(" "+ i);
        size--;
      }
    }
  }
  public static void main(String[] args) {
    Number obj = new Number();

    int n = 20;

    obj.display_ugly(n);

  }
}

 1
 2
 3
 4
 5
 6
 8
 9
 10
 12
 15
 16
 18
 20
 24
 25
 27
 30
 32
 36

#Python3 Program
#Display N Ugly Numbers
class Number :
  def factor(self, number, checker) :
    while (number % checker == 0) :
      number /= checker
    
    return number
  
  def is_ugly(self, number) :
    number = self.factor(number, 2)
    number = self.factor(number, 3)
    number = self.factor(number, 5)
    return number
  
  def display_ugly(self, size) :
    i = 1
    while (size > 0) :
      if (self.is_ugly(i) == 1) :
        print(" ", i)
        size -= 1

      i+=1
      
    
  
def main() :
  obj = Number()
  n = 20
  obj.display_ugly(n)
  

if __name__ == "__main__":
  main()

  1
  2
  3
  4
  5
  6
  8
  9
  10
  12
  15
  16
  18
  20
  24
  25
  27
  30
  32
  36

/*
  Node Js Program
  Display N Ugly Numbers
*/
class Number {
  factor(number, checker) {
    while (number % checker == 0) {
      number /= checker;
    }
    return number;
  }
  is_ugly(number) {
    number = this.factor(number, 2);
    number = this.factor(number, 3);
    number = this.factor(number, 5);
    return number;
  }
  display_ugly(size) {
    for (var i = 1; size > 0; ++i) {
      if (this.is_ugly(i) == 1) {
        console.log(" " + i);
        size--;
      }
    }
  }
}

function main() {
  var obj = new Number();
  var n = 20;
  obj.display_ugly(n);
}
main();

 1
 2
 3
 4
 5
 6
 8
 9
 10
 12
 15
 16
 18
 20
 24
 25
 27
 30
 32
 36

<?php
/*
  Php Program
  Display N Ugly Numbers
*/
class Number {

  public function factor($number, $checker) {
    while ($number % $checker == 0) {
      $number /= $checker;
    }
    return $number;
  }

  public function is_ugly($number) {
    $number = $this->factor($number, 2);
    $number = $this->factor($number, 3);
    $number = $this->factor($number, 5);
    return $number;
  }
  public function display_ugly($size) {
    for ($i = 1; $size > 0; ++$i) {
      if ($this->is_ugly($i) == 1) {
        echo ("\n". $i);
        $size--;
      }
    }
  }
}
function main() {
  $obj = new Number();
  $n = 20;
  $obj->display_ugly($n);
}
main();

1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
32
36

/*
  C# Program
  Display N Ugly Numbers
*/
using System;
public class Number {

  public int factor(int number, int checker) {
    while (number % checker == 0) {
      number /= checker;
    }
    return number;
  }
  int is_ugly(int number) {
    number = factor(number, 2);
    number = factor(number, 3);
    number = factor(number, 5);
    return number;
  }
  public void display_ugly(int size) {

    for (int i = 1; size > 0; ++i) {
      if (is_ugly(i) == 1) {
        Console.WriteLine(" " + i);
        size--;
      }
    }
  }
  public static void Main(String[] args) {
    Number obj = new Number();

    int n = 20;

    obj.display_ugly(n);

  }
}

 1
 2
 3
 4
 5
 6
 8
 9
 10
 12
 15
 16
 18
 20
 24
 25
 27
 30
 32
 36

#Ruby Program
#Display N Ugly Numbers
class Number 
  def factor(number, checker) 
    while (number % checker == 0) 
      number /= checker
    end
    return number
  end
  def is_ugly(number) 
    number = self.factor(number, 2)
    number = self.factor(number, 3)
    number = self.factor(number, 5)
    return number
  end
  def display_ugly(size) 
    i = 1 
    while (size > 0 ) 
      if (self.is_ugly(i) == 1) 
        print(i,"\n")
        size -= 1
      end
      i+=1
    end
  end
end
def main() 
  obj = Number.new()
  n = 20
  obj.display_ugly(n)
end
main()

1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
32
36

/*
  Swift 4
  Display N Ugly Numbers
*/
class Number {
  func factor(_ number: inout Int, _ checker: Int) {
    while (number % checker == 0) {
      number /= checker;
    }
    
  }
  func is_ugly(_ value: Int) -> Int {
    var number = value;
    self.factor(&number, 2);
    self.factor(&number, 3);
    self.factor(&number, 5);
    return number;
  }
  func display_ugly(_ size: Int) {
    var i: Int = 1;
    var num = size;
    while ( num > 0) {
      if (self.is_ugly(i) == 1) {
        print(" ", i);
        num -= 1;
      }
      i += 1;
    }
  }

}
func main() {
  let obj: Number = Number();
  let n: Int = 20;
  obj.display_ugly(n);
}
main();

  1
  2
  3
  4
  5
  6
  8
  9
  10
  12
  15
  16
  18
  20
  24
  25
  27
  30
  32
  36

Resultant Output Explanation

The output of the provided code for N = 20 is as follows:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

These are the first 20 ugly numbers in ascending order.

Time Complexity

Let's analyze the time complexity of the given code. The main loop in the display_ugly(size) function runs until the value of size becomes 0. For each i in the loop, we are calling the is_ugly(i) function to check if i is an ugly number or not. The is_ugly function repeatedly divides the input number by 2, 3, and 5 until it becomes not divisible by them.

The time complexity of the is_ugly function depends on the number itself. In the worst case, if the number has a large prime factor, the loop inside the is_ugly function may run multiple times. However, the loop is not infinite as we are dividing by 2, 3, and 5 only.

Therefore, the overall time complexity of the given code is approximately O(N * M), where N is the number of ugly numbers to be displayed, and M is the average number of divisions required to check if a number is ugly or not. In practice, M is usually small, and the code will run in a reasonable time for moderate values of N.