nᵗʰ丑数 [英] nᵗʰ ugly number
问题描述
质因数只有 2、3 或 5 的数称为丑数.
Numbers whose only prime factors are 2, 3, or 5 are called ugly numbers.
示例:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
1 可以认为是 2^0.
1 can be considered as 2^0.
我正在寻找第 nth 个丑陋的数字.请注意,随着 n
变大,这些数字的分布极其稀疏.
I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n
gets large.
我写了一个简单的程序来计算给定的数字是否丑陋.对于 n >500
- 它变得超级慢.我尝试使用备忘录 - 观察:ugly_number * 2
、ugly_number * 3
、ugly_number * 5
都是丑陋的.即便如此,它也很慢.我尝试使用 log 的一些属性 - 因为这会将这个问题从乘法减少到加法 - 但是,还没有多少运气.想到这里与大家分享.有什么有趣的想法吗?
I wrote a trivial program that computes if a given number is ugly or not. For n > 500
- it became super slow. I tried using memoization - observation: ugly_number * 2
, ugly_number * 3
, ugly_number * 5
are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?
使用类似于埃拉托色尼筛网的概念(感谢 Anon)
Using a concept similar to Sieve of Eratosthenes (thanks Anon)
for (int i(2), uglyCount(0); ; i++) {
if (i % 2 == 0)
continue;
if (i % 3 == 0)
continue;
if (i % 5 == 0)
continue;
uglyCount++;
if (uglyCount == n - 1)
break;
}
i
是第 nth 个丑陋的数字.
i
is the nth ugly number.
即使这样也很慢.我试图找到第 1500 个th 丑陋的数字.
Even this is pretty slow. I am trying to find the 1500th ugly number.
推荐答案
一个简单快速的 Java 解决方案.使用 Anon..
描述的方法这里 TreeSet
只是一个能够返回其中最小元素的容器.(没有存储重复项.)
A simple fast solution in Java. Uses approach described by Anon..
Here TreeSet
is just a container capable of returning smallest element in it. (No duplicates stored.)
int n = 20;
SortedSet<Long> next = new TreeSet<Long>();
next.add((long) 1);
long cur = 0;
for (int i = 0; i < n; ++i) {
cur = next.first();
System.out.println("number " + (i + 1) + ": " + cur);
next.add(cur * 2);
next.add(cur * 3);
next.add(cur * 5);
next.remove(cur);
}
由于第 1000 个丑数是 51200000,因此将它们存储在 bool[]
中并不是一个真正的选择.
Since 1000th ugly number is 51200000, storing them in bool[]
isn't really an option.
编辑
作为工作的消遣(调试愚蠢的 Hibernate),这是完全线性的解决方案.感谢 marcog 的创意!
int n = 1000;
int last2 = 0;
int last3 = 0;
int last5 = 0;
long[] result = new long[n];
result[0] = 1;
for (int i = 1; i < n; ++i) {
long prev = result[i - 1];
while (result[last2] * 2 <= prev) {
++last2;
}
while (result[last3] * 3 <= prev) {
++last3;
}
while (result[last5] * 5 <= prev) {
++last5;
}
long candidate1 = result[last2] * 2;
long candidate2 = result[last3] * 3;
long candidate3 = result[last5] * 5;
result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
}
System.out.println(result[n - 1]);
这个想法是为了计算a[i]
,我们可以使用a[j]*2
来表示一些j
我
.但我们还需要确保 1) a[j]*2 >a[i - 1]
和 2) j
是最小的.
然后,a[i] = min(a[j]*2, a[k]*3, a[t]*5)
.
The idea is that to calculate a[i]
, we can use a[j]*2
for some j < i
. But we also need to make sure that 1) a[j]*2 > a[i - 1]
and 2) j
is smallest possible.
Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)
.
这篇关于nᵗʰ丑数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!