相关疑难解决方法(0)

只有素数因子为2,3或5的数字称为丑陋数字.

例:

1,2,3,4,5,6,8,9,10,12,15 ......

1可以被认为是2 ^ 0.

我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.

我写了一个简单的程序来计算给定数字是否丑陋.对于n> 500 - 它变得超级慢.我尝试使用memoization - 观察:ugly_number*2,ugly_number*3,ugly_number*5都很难看.即便如此,它也很慢.我尝试使用log的一些属性 - 因为这会将这个问题从乘法减少到另外 - 但是,运气不大.想与大家分享这个.任何有趣的想法？

使用类似于"Eratosthenes的筛子"的概念(感谢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;
    }

我是第n个难看的数字.

即便这样也很慢.我想找到第1500个难看的数字.

在表达中

2 ^x*3 ^y*5 ^z

的x,y并且z可以采取非负整数值(> = 0).

因此该函数将生成一系列数字 1,2,3,4,5,6,8,9,10,12,15,16....

• 我有一个强力解决方案.
• 我基本上会在从1开始的循环中迭代,并且在每次迭代中我会发现当前的数字因子是否仅来自2,3或5的集合.

我想要的是一个优雅的算法.

这是一个面试问题.

我有一组素数,我必须使用递增顺序的那些素因子生成整数.

例如,如果集合是p = {2,5}那么我的整数应该是1,2,4,5,8,10,16,20,25 ......

有没有有效的算法来解决这个问题？