剣指offer全集详细解python版——丑数

素因数2,3,5のみを含む数を丑数(Ugly Number)と呼ぶ.例えば、6、8はすべて醜数であるが、14は質量因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
考え方:
前の数を利用して次の数を生み出す.3つのtmpを開くと、次の数を生成する可能性のある変数がそれぞれ格納されます.
コード:

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index == 0:
            return 0
        if index == 1:
            return 1
        elif index == 2:
            return 2
        elif index == 3:
            return 3
        elif index == 4:
            return 4
        else:
            c_num = [1,2,3,4]
            index_2 = 2
            index_3 = 1
            index_5 = 0
            for i in range(5, index+1):
                new_c = min(c_num[index_2]*2,c_num[index_3]*3,c_num[index_5]*5)
                for j in range(index_2, i):
                    if c_num[j]*2 > new_c:
                        index_2 = j
                        break
                for j in range(index_3, i):
                    if c_num[j]*3 > new_c:
                        index_3 = j
                        break
                for j in range(index_5, i):
                    if c_num[j]*5 > new_c:
                        index_5 = j
                        break
                c_num.append(new_c)
            return c_num[-1]