[原创代码] 无忧公主编程挑战003

happy886rr

　　无忧公主说这是超难题，所谓丑数，就是不能被2，3，5以外的其他素数整除的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。找出第1500个丑数。
　　百度一下，才知道，原来此题被诸如谷歌、微软、西门子等多家知名IT公司作为面试必考题目。个别博客更是贴出长达几十行的代码来解决该问题。看得我一头雾水。自认跟数颇有缘的我，经过一番推敲，发现一个捷径，怎么就没人想到啊！
　　好吧，直接说思路。丑数不就是只能被２、3、5整除的数吗,那么这个数一定能表示成为几个2乘几个3乘几个5。这不就是丑数的生成公式吗！即丑数Ugly=(2^a)*(3^b)*(5^c)。看着好眼熟，还可以等价成四维空间的立体的质量，看来我抽象能力太好了，毕竟经常想象四维空间的样子。直接四维空间求质度。其实for循环就足够用的，把a、b、c各循环30次，30*30*30将会产生27000个丑数，一排序，打印第1500个完事。但是能省就省是我喜欢做的事，取对数，变乘法为加法。循环步数估值lg3*b=lg2*30；lg5*c=lg2*30.好吧，看来b需要循环19次，c只需13次，省得真不多。不过运行速度给力啊，0.06秒，还是N年前的破赛扬。

# Python解无忧公主编程挑战003
print("第1500个丑数是",end=" ")
U=[]
U.append(1) #顶位
for a in range(0,30):
	for b in range(0,19):
		for c in range(0,13):
			Ugly_Num=(2**a)*(3**b)*(5**c)
			U.append(Ugly_Num)
R=sorted(U);print(R[1500])
复制代码

这么快就解决问题了，真搞不明白网上其他人为何会写几十行去解决问题。

虫子樱桃

数学差的人表示看不明白

CrLf

思路很赞，不过感觉指数运算花的时间太多了，空间换时间应能压缩到0.01秒以下

happy886rr

回复 3# CrLf
最好的解法是用图论，三叉树，1分叉为2、3、5，每个2、3、5再分叉。只要遍历第1000个节点就行。