寻找合数的最小因子

Question

如果给定一些质数：2、3、5、7 是否有一种有效的方法来查找大于某个给定数字的最小复合数，该复合数除允许的质数因子外没有其他质因子。

例如： 给定质数集合为：2、3、5、7。 如果我们要找到一个必须大于或等于85的组合数，并且除了2、3、5或7之外没有任何质因数，则答案应该是90，因为…

85 = 5 * 17 (wrong)  
86 = 2 * 43 (wrong)  
87 = 3 * 29 (wrong)  
88 = (2 ^ 3) * 11 (wrong)  
89 = 89 (wrong)  
90 = 2 * (3 ^ 2) * 5 (correct)

- Susan Doggie

---

为什么235*7不是答案？85是否作为算法的额外约束条件？为什么你没有使用7？ - Mohsen Kamrani

@Fallen：好的，现在我明白了。 - Mohsen Kamrani

你有多少个质数？它们总是某个k最小的质数吗？查询数字可以有多大？ - Niklas B.

@Niklas B.：因为我正在使用这个算法进行我的fft，所以我已经专门处理了数据长度为2、3、5、7的情况。 - Susan Doggie

@SusanDoggie：你能不能用一些好的修剪/回溯方法来暴力求解这些质数的指数？应该几乎是O(log n)。 - Niklas B.

Answer 1

对于小数的例子，暴力方法可能是可以的：从85开始测试所有数字。您不需要确定所有因子。只需通过对列表中的质数进行连续除法，看看是否能将一个数字 n 降至1即可。

另外，您也可以采用自下而上的方法：一个有效的合成数是：

2^a2 * 3^a3 * 5^a5 * 7^a7

现在您可以递归地探测所有集合{a2，a3，a5，a7}。从{0，0，0，0}开始，产生1和集合索引0。然后通过增加当前集合索引处的指数并增加集合索引来探测，如果这不意味着您超出列表的边界。当您遇到大于或等于阈值的数字时，请不要进一步递归。

伪代码如下：

function spread(p[], ix, num, lim)
{
    if (num >= lim) {
        return min;
    } else {
        m1 = spread(p, ix, k * p[ix], lim, min);

        ix++;
        if (ix == p.length) return m1

        m2 = spread(p, n, ix, num, lim, min);
        return min(m1, m2);
    }
}

min = spread([2, 3, 5, 7], 0, 1, 85)

这种方法在您的示例中无法带来太多收益，但对于更大的质数和情况应该更好，其中最小值不接近阈值。

- M Oehm

Answer 2

1. 从起始数字开始。

2. 使用简单除法因式分解当前数字。

3. 如果当前数字是合数且其所有因子都在给定列表中，则停止，当前数字就是答案。

4. 将当前数字加一。

5. 回到步骤2。

- David Schwartz

---

@SusanDoggie：显然不是，这个算法实现的顺序与最先进版本的状态为O(exp((64b/9)^1/3 (log b)^2/3) ，其中b为位数。 - Mohsen Kamrani

@SusanDoggie 我很确定这不是唯一的方法。 - David Schwartz

Answer 3

你需要找到最小的数2^i 3^j 5^k 7^l，它大于或等于某个N。

我们可以简单地按顺序处理这些数字，直到我们得到一个大于N的数字。

最小的数字是1，对应于(i,j,k,l)=(0,0,0,0)。现在我们将这个元组推入一个min-heap H并添加到一个集合S中（例如使用哈希表实现）。

现在我们重复以下步骤，直到找到一个大于N的数字：

• 从堆H中弹出最小的元素(i,j,k,l)
• 如果它们还没有在S中，则将元组(i+1,j,k,l)，(i,j+1,k,l)，(i,j,k+1,l)和(i,j,k,l+1)添加到H和S中。

这确保了我们按正确的顺序考虑数字，因为每次删除一个数字/元组时，我们将所有新的后继候选项添加到堆中。

以下是Python的实现：

import heapq
N = 85
S = set([(0,0,0,0)])
H = [( 1 , (0,0,0,0) )]
while True:
    val,(i,j,k,l) = heapq.heappop(H)
    if val >= N:
        break
    if (i+1,j,k,l) not in S:
        S.add((i+1,j,k,l))
        heapq.heappush(H,( val*2 , (i+1,j,k,l) ) )
    if (i,j+1,k,l) not in S:
        S.add((i,j+1,k,l))
        heapq.heappush(H,( val*3 , (i,j+1,k,l) ) )
    if (i,j,k+1,l) not in S:
        S.add((i,j,k+1,l))
        heapq.heappush(H,( val*5 , (i,j,k+1,l) ) )
    if (i,j,k,l+1) not in S:
        S.add((i,j,k,l+1))
        heapq.heappush(H,( val*7 , (i,j,k,l+1) ) )

print val # 90

由于序列的大小呈指数级增长，因此这将不超过O(log N)次迭代。在每次迭代中，我们最多向H和S添加3个项目，因此堆永远不会包含超过O(3 log N)个项目。每个堆/集操作的成本都不超过O(log log N)，从而确保整个时间复杂度为O(log N * log log N)。

- related