Count Ugly Numbers Below N

Problem

Count the ugly numbers strictly less than n, where an ugly number has no prime factors other than 2, 3 and 5 and 1 counts as ugly.

For every candidate, divide out all factors of 2, 3 and 5 and check whether 1 remains. Return 0 for n <= 1.

Hint

Only 7 is missing from 1 through 9, since 7 has a prime factor outside the allowed set.

case 1

in: [1]

expected: 0

case 2

in: [10]

expected: 8

case 3

in: [12]

expected: 9

case 4

in: [30]

expected: 17

case 5

in: [0]

expected: 0

Starter codePython

def count_ugly_below(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor