Ugly Numbers/남훈

1500 "번째" ugly number 를 알기 위해서는 1499 번째 ugly number 보다 큰 수 중에 해당되는 수가 있는지 조사하면 된다. 그런 간단한 아이디어로 구현

ver. 1

def exponent(num, div):
	expo = 0
	while True:
		if num % div != 0:
			return expo
		num /= div
		expo += 1

def is_ugly(num):
	two = exponent(num, 2)
	three = exponent(num, 3)
	five = exponent(num, 5)

	if num == (2 ** two) * (3 ** three) * (5 ** five):
		return True
	
	return False

def ugly(num):
	if num <= 0:
		return 0
	
	prev = ugly(num - 1)
	guess = prev + 1

	while True:
		if is_ugly(guess):
			return guess
		guess += 1


goal = 1500

print "The " + `goal` + "(st/nd/th) ugly number is " + `ugly2(goal)`

UglyNumbers