丑陋的数字 [英] 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.

我正在寻找第n 个丑陋的数字.请注意，随着 n 变大，这些数字的分布极为稀疏.

I am working on finding n^th 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?

使用类似于 Eratosthenes筛子(感谢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 是第n个 丑陋数字.

即使这很慢.我试图找到第1500个 丑陋的数字.

Even this is pretty slow. I am trying to find the 1500^th 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] ，我们可以对某些 j< a使用 a [j] * 2 .我.但我们还需要确保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).

这篇关于丑陋的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！