Skip to main content

Print Ugly Numbers

Ugly numbers are positive integers whose prime factors are limited to 2, 3, and 5. In other words, an ugly number can be expressed as (2^a) x (3^b) x (5^c), where a, b, and c are non-negative integers. The first few ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, and so on.

Ugly numbers are important in computer science and mathematics because they have a significant role in dynamic programming, as well as in various algorithmic and computational problems. They are used to solve problems related to finding the nth term in a sequence or finding the smallest multiple that has only 2, 3, and 5 as prime factors.

The concept of ugly numbers is used in many real-life applications, such as in digital signal processing and image processing, where the efficient representation of signals and images can be done using the properties of ugly numbers.

Write an algorithm which print n ugly numbers.

For example.

Input  : N = 10
Output :  1 2 3 4 5 6 8 9 10 12

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

Note that 1 is typically treated as an ugly number. Here given code implementation process.

// C Program
// Print Ugly Numbers
// By dynamic programming
#include <stdio.h>

// Returns minimum value of two numbers
int find_min(int a, int b)
{
    if (a > b)
    {
        //when b is small
        return b;
    }
    //when a is small
    return a;
}
void ugly_number(int n)
{
    // initial values 
    int no_2 = 2, no_3 = 3, no_5 = 5;
    // initial values of three location
    int two = 0, three = 0, five = 0;
    // Use to store N ugly numbers
    int collection[n];
    // Set first ugly number
    collection[0] = 1;
    for (int i = 1; i < n; ++i)
    {
        // Assign that minimum value of three numbers
        collection[i] = find_min(no_2, find_min(no_3, no_5));
        if (no_2 == collection[i])
        {
            two++;
            no_2 = collection[two] *2;
        }
        if (no_3 == collection[i])
        {
            three++;
            no_3 = collection[three] *3;
        }
        if (no_5 == collection[i])
        {
            five++;
            no_5 = collection[five] *5;
        }
    }
    // Display ugly number
    for (int i = 0; i < n; ++i)
    {
        printf("%d  ", collection[i]);
    }
}
int main()
{
    int n = 20;
    ugly_number(n);
    return 0;
}

Output

1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
// Java Program
// Print Ugly Numbers
// By dynamic programming
public class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public int findMin(int a, int b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    public void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2, no_3 = 3, no_5 = 5;
        // initial values of three location
        int two = 0, three = 0, five = 0;
        // Use to store N ugly numbers
        int[] collection = new int[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = findMin(no_2, findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            System.out.print(" " + collection[i]);
        }
    }
    public static void main(String[] args)
    {
        PrintUglyNumber task = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
package main
import "fmt"
// Go Program
// Print Ugly Numbers
// By dynamic programming
type PrintUglyNumber struct {}
func getPrintUglyNumber() * PrintUglyNumber {
    var me *PrintUglyNumber = &PrintUglyNumber {}
    return me
}
// Returns minimum value of two numbers
func(this PrintUglyNumber) findMin(a, b int) int {
    if a > b {
        // When b is small
        return b
    }
    // When a is small
    return a
}
func(this PrintUglyNumber) uglyNumber(n int) {
    // initial values 
    var no_2 int = 2
    var no_3 int = 3
    var no_5 int = 5
    // initial values of three location
    var two int = 0
    var three int = 0
    var five int = 0
    // Use to store N ugly numbers
    var collection = make([] int, n)
    // Set first ugly number
    collection[0] = 1
    for i := 1 ; i < n ; i++ {
        // Assign that minimum value of three numbers
        collection[i] = this.findMin(no_2, this.findMin(no_3, no_5))
        if no_2 == collection[i] {
            two++
            no_2 = collection[two] * 2
        }
        if no_3 == collection[i] {
            three++
            no_3 = collection[three] * 3
        }
        if no_5 == collection[i] {
            five++
            no_5 = collection[five] * 5
        }
    }
    //Display ugly number
    for i := 0 ; i < n ; i++ {
        fmt.Print(" ", collection[i])
    }
}
func main() {
    var task * PrintUglyNumber = getPrintUglyNumber()
    // Test Case
    task.uglyNumber(20)
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    public:
        // Returns minimum value of two numbers
        int findMin(int a, int b)
        {
            if (a > b)
            {
                // When b is small
                return b;
            }
            // When a is small
            return a;
        }
    void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2;
        int no_3 = 3;
        int no_5 = 5;
        // initial values of three location
        int two = 0;
        int three = 0;
        int five = 0;
        // Use to store N ugly numbers
        int collection[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this->findMin(no_2, 
                            this->findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] *2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] *3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] *5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            cout << " " << collection[i];
        }
    }
};
int main()
{
    PrintUglyNumber *task = new PrintUglyNumber();
    // Test Case
    task->uglyNumber(20);
    return 0;
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Include namespace system
using System;
// Csharp Program
// Print Ugly Numbers
// By dynamic programming
public class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public int findMin(int a, int b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    public void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2;
        int no_3 = 3;
        int no_5 = 5;
        // initial values of three location
        int two = 0;
        int three = 0;
        int five = 0;
        // Use to store N ugly numbers
        int[] collection = new int[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            Console.Write(" " + collection[i]);
        }
    }
    public static void Main(String[] args)
    {
        PrintUglyNumber task = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
<?php
// Php Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public  function findMin($a, $b)
    {
        if ($a > $b)
        {
            // When b is small
            return $b;
        }
        // When a is small
        return $a;
    }
    public  function uglyNumber($n)
    {
        // initial values 
        $no_2 = 2;
        $no_3 = 3;
        $no_5 = 5;
        // initial values of three location
        $two = 0;
        $three = 0;
        $five = 0;
        // Use to store N ugly numbers
        $collection = array_fill(0, $n, 0);
        // Set first ugly number
        $collection[0] = 1;
        for ($i = 1; $i < $n; ++$i)
        {
            // Assign that minimum value of three numbers
            $collection[$i] = $this->findMin(
              $no_2, $this->findMin($no_3, $no_5));
            if ($no_2 == $collection[$i])
            {
                $two++;
                $no_2 = $collection[$two] * 2;
            }
            if ($no_3 == $collection[$i])
            {
                $three++;
                $no_3 = $collection[$three] * 3;
            }
            if ($no_5 == $collection[$i])
            {
                $five++;
                $no_5 = $collection[$five] * 5;
            }
        }
        //Display ugly number
        for ($i = 0; $i < $n; ++$i)
        {
            echo(" ".strval($collection[$i]));
        }
    }
}

function main()
{
    $task = new PrintUglyNumber();
    // Test Case
    $task->uglyNumber(20);
}
main();

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Node JS Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    findMin(a, b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    uglyNumber(n)
    {
        // initial values 
        var no_2 = 2;
        var no_3 = 3;
        var no_5 = 5;
        // initial values of three location
        var two = 0;
        var three = 0;
        var five = 0;
        // Use to store N ugly numbers
        var collection = Array(n).fill(0);
        // Set first ugly number
        collection[0] = 1;
        for (var i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, 
                            this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (var i = 0; i < n; ++i)
        {
            process.stdout.write(" " + collection[i]);
        }
    }
}

function main()
{
    var task = new PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}
main();

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
#  Python 3 Program
#  Print Ugly Numbers
#  By dynamic programming

class PrintUglyNumber :
    #  Returns minimum value of two numbers
    def findMin(self, a, b) :
        if (a > b) :
            #  When b is small
            return b
        
        #  When a is small
        return a
    
    def uglyNumber(self, n) :
        #  initial values 
        no_2 = 2
        no_3 = 3
        no_5 = 5
        #  initial values of three location
        two = 0
        three = 0
        five = 0
        #  Use to store N ugly numbers
        collection = [0] * (n)
        #  Set first ugly number
        collection[0] = 1
        i = 1
        while (i < n) :
            #  Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, self.findMin(no_3, no_5))
            if (no_2 == collection[i]) :
                two += 1
                no_2 = collection[two] * 2
            
            if (no_3 == collection[i]) :
                three += 1
                no_3 = collection[three] * 3
            
            if (no_5 == collection[i]) :
                five += 1
                no_5 = collection[five] * 5
            
            i += 1
        
        i = 0
        # Display ugly number
        while (i < n) :
            print(" ", collection[i], end = "")
            i += 1
        
    

def main() :
    task = PrintUglyNumber()
    #  Test Case
    task.uglyNumber(20)

if __name__ == "__main__": main()

Output

  1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
#  Ruby Program
#  Print Ugly Numbers
#  By dynamic programming

class PrintUglyNumber 
    #  Returns minimum value of two numbers
    def findMin(a, b) 
        if (a > b) 
            #  When b is small
            return b
        end

        #  When a is small
        return a
    end

    def uglyNumber(n) 
        #  initial values 
        no_2 = 2
        no_3 = 3
        no_5 = 5
        #  initial values of three location
        two = 0
        three = 0
        five = 0
        #  Use to store N ugly numbers
        collection = Array.new(n) {0}
        #  Set first ugly number
        collection[0] = 1
        i = 1
        while (i < n) 
            #  Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, 
                            self.findMin(no_3, no_5))
            if (no_2 == collection[i]) 
                two += 1
                no_2 = collection[two] * 2
            end

            if (no_3 == collection[i]) 
                three += 1
                no_3 = collection[three] * 3
            end

            if (no_5 == collection[i]) 
                five += 1
                no_5 = collection[five] * 5
            end

            i += 1
        end

        i = 0
        # Display ugly number
        while (i < n) 
            print(" ", collection[i])
            i += 1
        end

    end

end

def main() 
    task = PrintUglyNumber.new()
    #  Test Case
    task.uglyNumber(20)
end

main()

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Scala Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber()
{
    // Returns minimum value of two numbers
    def findMin(a: Int, b: Int): Int = {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    def uglyNumber(n: Int): Unit = {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        var collection: Array[Int] = Array.fill[Int](n)(0);
        // Set first ugly number
        collection(0) = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection(i) = findMin(no_2, findMin(no_3, no_5));
            if (no_2 == collection(i))
            {
                two += 1;
                no_2 = collection(two) * 2;
            }
            if (no_3 == collection(i))
            {
                three += 1;
                no_3 = collection(three) * 3;
            }
            if (no_5 == collection(i))
            {
                five += 1;
                no_5 = collection(five) * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" " + collection(i));
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: PrintUglyNumber = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Swift 4 Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    func findMin(_ a: Int, _ b: Int) -> Int
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    func uglyNumber(_ n: Int)
    {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        var collection: [Int] = Array(repeating: 0, count: n);
        // Set first ugly number
        collection[0] = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, self.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two += 1;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three += 1;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five += 1;
                no_5 = collection[five] * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" ", collection[i], terminator: "");
            i += 1;
        }
    }
}
func main()
{
    let task: PrintUglyNumber = PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}
main();

Output

  1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
// Kotlin Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    fun findMin(a: Int, b: Int): Int
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    fun uglyNumber(n: Int): Unit
    {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        val collection: Array < Int > = Array(n)
        {
            0
        };
        // Set first ugly number
        collection[0] = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, 
                             this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two += 1;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three += 1;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five += 1;
                no_5 = collection[five] * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" " + collection[i]);
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val task: PrintUglyNumber = PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}

Output

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




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment