在给定其主要因子但指数未知的情况下如何生成数字? [英] how to generate numbers given their prime factors, but with unknown exponents?
问题描述
Possible Duplicates:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)
我想知道如何快速而优雅地解决此问题:
I'm wondering how to solve this problem in a fast and elegant way:
我们定义每个数字 n 为丑陋"，其形式为:2 ^ x * 3 ^ y * 5 ^ z ;，其中x，y和z是自然数.找到第1500个丑陋的数字.
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.
例如第一个丑陋"的数字是:
E.g. the first "ugly" numbers are:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
我试图通过暴力方式解决此问题:
I've tried to solve this problem using brute-force, in this way:
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
但是它要花很多时间，我想找到一个更快，更好的解决方案.
But it takes quite a lot of time, and I'd like to find a faster and better solution.
我知道丑陋数字的主要因素，但是我想不出一种按照正确顺序生成这些数字的方法.
I know the prime factors of ugly numbers, but I can't think of a way to generate these numbers following the correct order.
我认为必须有一种无需检查所有数字即可生成这些数字的方法.问题在于，主要因子的指数似乎很随机地分布.
I think there must be a way to generate these numbers without having to check all the numbers. The problem is that it seems like exponents of the prime factors are distributed quite randomly.
看这张桌子:
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值似乎没有遵循任何规则.
As you can see x,y and z values don't seem to follow any rule.
你们中的某人能找到解决此问题的任何方法吗?
Can someone of you find any solution to this problem?
我正在考虑尝试将问题分成不同的部分. 由于问题是由指数的随机性决定的，因此我可以尝试独立生成2s，3s，5s的幂，然后生成2 ^ x * 3 ^ y，2 ^ x * 5 ^ z等形式的数. 最后将它们放在一起，但我不知道这是否能解决我的问题.
I'm thinking of trying to divide the problem in different parts. Since the problem is determined by the randomness of exponents, I could try to generate independently the powers of 2s,3s,5s and then the numbers of the form 2^x*3^y,2^x*5^z etc. And finally put them together, but I don't know if this will solve my issue.
推荐答案
这是一个完整的解决方案. O(n)复杂度，它会按顺序一次生成每个数字.
Here is a complete solution. O(n) complexity, it generates every number once and in order.
# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
n = 15
bases = [2, 3, 5]
nums = [1] * n
candidates_indexes = [0 for _ in bases]
candidates = [base for base in bases]
for i in range(1, n):
nextn = min(candidates)
nums[i] = nextn
for index, val in enumerate(candidates):
if val == nextn:
candidates_indexes[index] += 1
candidates[index] = bases[index] * nums[candidates_indexes[index]]
print(nums)
这篇关于在给定其主要因子但指数未知的情况下如何生成数字?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
