按小于 x 的一组数字列出所有可能的倍数的算法

Question

我正在努力解决一个更大的算法的子问题，我真的在努力解决这个问题!

问题

如果我有一个数字数组(比如 A)，我如何有效地列出所有可以通过将数字相乘而得到的数字(可以根据需要多次使用) ) 并且小于另一个数字(例如 x)。

例如，假设我有 A = [7, 11, 13] 并且 x 是 1010，答案将是:

 - 7 = 7
 - 11 = 11
 - 13 = 13
 - 7*7 = 49
 - 7*11 = 77
 - 7*13 = 91
 - 11*11 = 121
 - 11*13 = 143
 - 13*13 = 169
 - 7*7*7 = 343
 - 7*7*11 = 539
 - 7*7*13 = 637
 - 7*11*11 = 847
 - 7*11*13 = 1001

我尽力不遗漏任何内容(但如果有，请随时编辑)!

我可以看出这可能是某种类型的递归，但我真的很挣扎!

可选

天真的解决方案也很好(这就是我的挣扎)。

运行时间也是可选的。

更新

A中的所有数都是通过埃拉托色尼筛法得到的素数(1、2、3、5除外)。

更新 2

A也是有序的

更新 3A中的所有数字都在限制范围内

更新 4解决方案不需要递归。那只是我的一个想法。 Java 或伪代码更可取!

Answer 1

我会使用队列。我想到的算法类似于以下内容(伪代码):

multiplyUntil(A, X)
{
    queue q = A.toQueue();
    result;

    while(!q.isEmpty())
    {
        element = q.pop();
        result.add(element); // only if the initial elements are guaranteed to be < X otherwise you should add other checks

        for(int i = 0; i < A.length; i++)
        {
            product = element * A[i];

            // A is sorted so if this product is >= X the following will also be >= X
            if(product >= X)
            {
                // get out of the inner cycle
                break;
            }

            q.add(product);
        }
    }

    return result;
}

如果有什么不清楚的地方，请告诉我。

P.S:请记住，不能保证结果是排序的。如果您希望对结果进行排序，您可以使用堆而不是队列，或者在计算结束时对结果进行排序。