# coding: utf-8           使用学习生长法进行思考，  认真开始分析，  题不在多，在于精

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

     分析：   很明显还是从数字规律来  考虑，而不可能是直接遍历，该怎么利用这一规律呢？
              因为都是只包含2、3、5因子，所以这里的规律就是：因为丑数的因子只有 2    3   或者  5，所以丑数必定是 某个丑数 k 的 2倍、3倍、或者 5倍。
     思路：   所有丑数都是由前面丑数乘上2,或3,或5得到的。因此丑数按从小到大顺序排列，初始化一个丑数数组a[0...n-1]，以及三个临时索引i,j,k.
              计算a[n] = min{2*a[i], 3*a[j], 5*a[k]}.,并min{2*a[i], 3*a[j], 5*a[k]} > 2*a[i]或min{2*a[i], 3*a[j], 5*a[k]} > 3*a[j]或 min{2*a[i], 3*a[j], 5*a[k]} > 5*a[k]情况下，更新i，j，k。


'''

def  fun(n):
    #定义丑数 容器ugly，我们需要有1500个丑数
    ugly=[1]
    #定义三个临时索引
    t2=t3=t5=0

    #这个循环非常有意思
    while len(ugly)<n:
        #对于每次  找丑数都是在已有的丑数序列中，利用三个索引从前往后搜【不是从头，是从现有的前开始】，  三个索引对应三种情况，只需要找到大于之前丑数的  对应最小的即可。方法稳稳的
        #2 3 5这三个可以对应不同的各自的索引 找序列
        while ugly[t2]*2<ugly[-1]:
            t2+=1
        while ugly[t3]*3<ugly[-1]:
            t3+=1
        while ugly[t5]*5<ugly[-1]:
            t5+=1
        ugly.append(min(ugly[t2]*2,ugly[t3]*3,ugly[t5]*5))

    return ugly[-1]

