**C Program** / **Algorithm** for Ugly Numbers: **What **is an** Ugly Number Series**? **Ugly Numbers** are the ones whose prime factors are 2,3 or 5 Only. We have also given a Java Source code in Method #4

So Ugly Number Series is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and so on…

The reason why 1 is added is because of the old convention and mostly 1 is added in many series may it be a Fibonacci series.

## Ugly Numbers Source Code in C

- Program #1
# include<stdio.h> # include<stdlib.h> /*This function divides n1 by greatest divisible power of n2*/ int Primefact(int n1, int n2) { while (n1%n2 == 0) n1 = n1/n2; return n1; } /* Function to check if n1 number is ugly or not */ int isUglyNumber(int num) { num = Primefact(num, 2); num = Primefact(num, 3); num = Primefact(num, 5); return (num == 1)? 1 : 0; } /* Function to get the nth ugly number*/ int nthUglynum(int n) { int j = 1; int count = 1; /* a temporary variable to count Ugly Number*/ /*To check all the numbers until n*/ while (n > count) { j++; if (isUglynum(j)) count++; // since i is ugly number thus count=count+1 } return i; } int main() { int get; printf("Program for nth Ugly Number! Enter value of n"); scanf("%d";&get); printf("%d ugly number is= %d",nthuglynum(get)); return 0; }

This approach has a time complexity of Big-O-Notation O(n).

Splitting the Ugly number sequence of 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …into three groups –

- 1×2, 2×2, 3×2, 4×2, 5×2 . . .
- 1×3, 2×3, 3×3, 4×3, 5×3 . . .
- 1×5, 2×5, 3×5, 4×5, 5×5 . . .

since each number can be divided by 2, 3, 5 only

We can find that every sub sequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.

# include<stdio.h> # include<stdlib.h> # define bool int /* Function to find minimum of 3 numbers */ int min(int , int , int ); /* Function to get the nth ugly number*/ int getNthUglyNo(int n) { int *ugly = (int *)(malloc (sizeof(int)*n)); int i2 = 0, i3 = 0, i5 = 0; int i; int n2= 2; // where n2= multiple of 2 int n3= 3; // where n3=multiple of 3 int n5= 5;//where n5=multiple of 5 int next_uglynum = 1; *(ugly+0) = 1; for(i=1; i<n; i++) { next_uglynum = min(n2, n3,n5); *(ugly+i) = next_uglynum; if(next_uglynum == n2) { i2 = i2+1; n2 = *(ugly+i2)*2; } if(next_uglynum == n3) { i3 = i3+1; n3 = *(ugly+i3)*3; } if(next_uglynum == n5) { i5 = i5+1; n5 = *(ugly+i5)*5; } } /*End of for loop (i=1; i<n; i++) */ return next_uglynum; } /* Function to find minimum of 3 numbers */ int min(int a, int b, int c) { if(a <= b) { if(a <= c) return a; else return c; } if(b <= c) return b; else return c; } /* Driver program to test above functions */ int main() { int no = getNthUglyNo(150); printf("%dth ugly no. is %d ", 150, no); getchar(); return 0; }

**Explanation:**initializing the array ugly[] = | 1 | i2 = i3 = i5 = 0; First iteration ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(2, 3, 5) = 2 ugly[] = | 1 | 2 | i2 = 1, i3 = i5 = 0 (i2 is incremented ) Second iteration ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(4, 3, 5) = 3 ugly[] = | 1 | 2 | 3 | i2 = 1, i3 = 1, i5 = 0 (i3 is incremented ) Third iteration ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(4, 6, 5) = 4 ugly[] = | 1 | 2 | 3 | 4 | i2 = 2, i3 = 1, i5 = 0 (i2 is incremented ) Fourth iteration ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(6, 6, 5) = 5 ugly[] = | 1 | 2 | 3 | 4 | 5 | i2 = 2, i3 = 1, i5 = 1 (i5 is incremented ) Fifth iteration ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(6, 6, 10) = 6 ugly[] = | 1 | 2 | 3 | 4 | 5 | 6 | i2 = 3, i3 = 2, i5 = 1 (i2 and i3 is incremented ) and so on.. to the value give by the user

.

- This is a trivial program.
for (int a(2), uglyCount(0); ; a++) { if (a % 2 == 0) continue; if (a % 3 == 0) continue; if (a % 5 == 0) continue; uglyCount++; if (uglyCount == n - 1) break; }

**Java Program:**We have also listed a**Ugly Number java Source code**. This is a linear Solution of the Ugly Number series.int n = 1000; int last2 = 0; int last3 = 0; int last5 = 0; long[] ugly_no = new long[n]; ugly_no[0] = 1; for (int i = 1; i < n; ++i) { long prev = ugly_no[i - 1]; while (ugly_no[last2] * 2 <= prev) { ++last2; } while (ugly_no[last3] * 3 <= prev) { ++last3; } while (ugly_no[last5] * 5 <= prev) { ++last5; } long temp1 = ugly_no[last2] * 2; long temp2 = ugly_no[last3] * 3; long temp3 = ugly_no[last5] * 5; ugly_no[i] = Math.min(temp1, Math.min(temp2, temp3)); } System.out.println(ugly_no[n - 1]);

Also see:

Ugly Number C Program

Ugly Number Java Program

1 billionth ugly number:

62565096724471903888424537973014890491686968126921250076541212862080934425144389

76692222667734743108165348546009548371249535465997230641841310549077830079108427

08520497989078343041081429889246063472775181069303596625038985214292236784430583

66046734494015674435358781857279355148950650629382822451696203426871312216858487

7816068576714140173718