丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解答

丑数的正整数集合，比如2，3，5，2*2，2*3，2*5，3*5，2*2*2.。。。

# coding:utf-8
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        indexli = [1]
        l2 = 0
        l3 = 0
        l5 = 0
        for i in range(index-1):
            ret = min(indexli[l2]*2, indexli[l3]*3, indexli[l5]*5)
            indexli.append(ret)
            if ret % 2 == 0:
                l2 += 1
            if ret % 3 == 0:
                l3 += 1
            if ret % 5 == 0:
                l5 += 1
        return indexli[-1]


s = Solution()
print s.GetUglyNumber_Solution(3)

结束！