Ugly Numbers

Every once in a while I come across a coding problem that is tagged easy, but can prove difficult when chasing a red herring

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

There are two paths to a solution here -

• prove the number is not ugly
• prove the number is ugly

The first path requires searching for a Prime number greater than 5 and then checking if that Prime is a factor. In order to do this we would need to generate all Primes until at least half the original number.

The second path is far simpler

A number is made up of a number of a factors.

We can extract all the 2s , all the 3s and all the 5s from the number. Note - we extract all the 4s by extracting all the 2s. 

We are left with a number that can be one of either 3 choices -

• The number 1, in which case this is a ugly number or,
• A number that is not divisible by 2 , 3 or 5 - 
• either another Prime or 
• a number that is made up of other Primes

Code

The code as described above involves extracting all the 2s, 3s and 5s until we end up with a 1 or some other number

def isUgly(n):
   
    if n == 0: 
        return False

    # a number is ugly when it's prime factors are limited
    # to 2 and/or 3 and/or 5

    while n % 2 == 0: n = n / 2
    while n % 3 == 0: n = n / 3
    while n % 5 == 0: n = n / 5

    return n == 1