<分区>
Possible Duplicates:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)
我想知道如何以快速而优雅的方式解决这个问题:
We define "ugly" every number n which can be written in the form: 2^x * 3^y * 5^z;, where x,y and z are natural numbers. Find the 1500th ugly number.
例如第一个“丑陋”的数字是:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
我试过用蛮力解决这个问题，方法是这样的:
import itertools as it
def is_ugly(n):
'''Return `True` if *n* is an ugly number.'''
if n == 1:
return True
while not n % 2:
n //= 2
while not n % 3:
n //= 3
while not n % 5:
n //= 5
return n == 1
def nth_ugly(n):
'''Return the nth ugly number.'''
num = 0
for i in it.count(1):
if is_ugly(i):
num += 1
if num == n:
return i
但这需要相当多的时间，我想找到一个更快更好的解决方案。
我知道丑数的素因数，但我想不出一种方法来按照正确的顺序生成这些数字。
我认为必须有一种方法可以生成这些数字而不必检查所有数字。问题是质因子的指数似乎是随机分布的。
看这张表:
n |number| x | y | z |
------------------------
1 | 1 | 0 | 0 | 0 |
------------------------
2 | 2 | 1 | 0 | 0 |
------------------------
3 | 3 | 0 | 1 | 0 |
------------------------
4 | 4 | 2 | 0 | 0 |
------------------------
5 | 5 | 0 | 0 | 1 |
------------------------
6 | 6 | 1 | 1 | 0 |
------------------------
7 | 8 | 3 | 0 | 0 |
------------------------
8 | 9 | 0 | 2 | 0 |
------------------------
9 | 10 | 1 | 0 | 1 |
------------------------
10 | 12 | 2 | 1 | 0 |
------------------------
11 | 15 | 0 | 1 | 1 |
------------------------
12 | 16 | 4 | 0 | 0 |
------------------------
13 | 18 | 1 | 2 | 0 |
------------------------
14 | 20 | 2 | 0 | 1 |
------------------------
15 | 24 | 3 | 1 | 0 |
------------------------
如您所见，x、y 和 z 值似乎不遵循任何规则。
你们中有人能找到解决这个问题的方法吗？
我正在考虑尝试将问题分成不同的部分。 由于问题是由指数的随机性决定的，我可以尝试独立生成 2s、3s、5s 的幂，然后生成 2^x*3^y、2^x*5^z 等形式的数字。 最后把它们放在一起，但我不知道这是否能解决我的问题。