Posted on by Kalkicode
Code Number

# 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 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;
}```
```

#### Output

``````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);
}```
```

#### Output

`` 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);

}
}```
```

#### Output

`````` 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()```
```

#### Output

``````  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();```
```

#### Output

`````` 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();```
```

#### Output

``````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);

}
}```
```

#### Output

`````` 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()
```
```

#### Output

``````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();```
```

#### Output

``````  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.

## 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.

Categories
Relative Post