class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0:
            return
        if n==1:
            return 1
        k=[0 for i in range(n)]
        k[0]=1
        t2,t3,t5=0,0,0
        for i in range(1,n,1):
            k[i]=min(k[t2]*2,k[t3]*3,k[t5]*5)
            if k[i]==k[t2]*2: t2+=1
            if k[i] == k[t3] * 3: t3 += 1
            if k[i] == k[t5] * 5: t5 += 1
        return k[n-1]
s=Solution()
n=10
print(s.nthUglyNumber(n))
#每个ugly number都由原来的ugly number *2，*3，*5得到