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)`

리커시브 콜 하다가 뻗어버림

동일한 아이디어를 유지하되, 반복으로 처리

def is_ugly2(num):
	while True:
		if num == 1:
			return True
		elif num % 2 == 0:
			num /= 2
		elif num % 3 == 0:
			num /= 3
		elif num % 5 == 0:
			num /= 5
		else:	
			return False
		
def ugly3(num):
	if num < 1:
		return 0

	prev = iter = 1
	
	while True:
		if iter == num:
			return prev
		
		guess = prev + 1

		while True:
			if is_ugly2(guess):
				prev = guess
				break
			guess += 1

		iter += 1


goal = 1500

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

느림.

UglyNumbers