寻找丑数

[编程题]寻找丑数

热度指数：4893 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

整数N

输出描述:

第N个丑数

示例1

输入

输出

算法知识视频讲解

Python

华科平凡

python一行解法

print(sorted([2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)])[int(input())-1] )

编辑于 2019-02-24 13:57:06 回复(5)

Python

12138201808280808525

def fun(N):
    result = [1]
    i = 1
    count = 1
    while count < N:
        i += 1
        j = i
        while j%2 == 0:
            if j!=1:
                j = j / 2
                if j == 1:
                    result.append(i)
                    count += 1
                    break
        while j%2!=0 and j%3==0:
            if j!=1:
                j = j / 3
                if j == 1:
                    result.append(i)
                    count += 1
                    break
        while j%2!=0 and j%3!=0 and j%5==0:
            if j!=1:
                j = j / 5
                if j == 1:
                    result.append(i)
                    count += 1
                    break
    return result[N-1]
inp = input()
inp = int(inp)
print(fun(inp))

发表于 2018-09-04 16:40:06 回复(1)