# Ugly Number

published

last modified

2kb

Today I solved another `c++`

leetcode problem. This one was an *easy*. and asked us to determine whether a number was an *ugly number*. The idea is, a number is ugly if **it's prime factorisation** only consists of `2, 3, 5`

.

*One way to factorise a number into it's primes is to just pick the smallest possible prime number and divide this number by that prime and do the same and so on until the number is 1.*

## Wrong Way to Go

I originally went ahead and tried to find an algorithm that could produce all prime factors of a number and check to see if it only consisted of `2, 3, 5`

. This was not the right way to go.

## The Simple Solution

It was simple to realise that all we needed to do was continually check if this number `n`

was divisable with `mod = 0`

for any of those primes. If we eventually got to `1`

it meant that we could factorise `n`

with only `2, 3, 5`

if this check broke and `n`

was not equal to one, that meant other factors exist for `n`

and it isn't ugly (which isn't the worst thing for a number. Nobody likes being called ugly).

## Contact

If you have any comments or thoughts you can reach me at any of the places below.