确定可分解为 2^p5^q 的数字集的算法

Question

我正在尝试编写一种算法，该算法可以 return 小于实例 n 的正整数集，并且可以分解为 2^p5 ^q。我的数学不是最好的，所以我不知道如何确定一个数字是否可以以这种特定形式分解...

任何帮助将不胜感激:)

Answer 1

使用两个队列：q1, q2.

从 q1,q2 空开始。

（下面定义q.head() == 1，如果q为空，只在第一次迭代时需要）

Repeat while `min{q1.head(), q2.head()} <n`:
    let x = min{q1.head(), q2.head()}
    yield x
    remove x from relevant queue
    q1.add(x*2)
    q2.add(x*5)

这个想法是，如果 x1 在 x2 之前被处理，那么它意味着 x1<x2，因此 x1*2 < x2*2 和 x1*5 < x2*5 - 所以队列保持秩序，您在每个点要做的就是检查每个步骤应轮询哪些队列，这非常简单。

请注意，您也可以通过这种方式轻松地 trim 复制，因为数字是按顺序生成的，如果它与最后一个数字相同，则只需跳过数字即可已处理。

此解决方案的优点：

此解决方案的复杂性与元素数量呈线性关系生产。
生成的列表已经排序，如果您需要的话。
如果您需要 k 个第一个元素，此解决方案非常有效，因为它在 O(k) 中运行，您只需在生成第 k 个元素后中断。

Answer 2

I have no idea how I can determine whether a number can be factorised in this specific form

与其测试给定数字是否可以因式分解和运行通过所有小于 n 的数字，不如直接生成它们，例如：

void findNumbers(int n)
{
    int p = 0;
    int power2 = 1; 
    while(power2 < n)
    {
        int q = 0;
        int power5 = 1;
        while(power5 * power2 < n)
        {
            printf("%d p = %d q = %d\n", power5 * power2, p, q);
            power5 *= 5;
            q++;
        }
        power2 *= 2;
        p++;
    }
}

n = 500 的输出：

1 p = 0 q = 0
5 p = 0 q = 1
25 p = 0 q = 2
125 p = 0 q = 3
2 p = 1 q = 0
10 p = 1 q = 1
50 p = 1 q = 2
250 p = 1 q = 3
4 p = 2 q = 0
20 p = 2 q = 1
100 p = 2 q = 2
8 p = 3 q = 0
40 p = 3 q = 1
200 p = 3 q = 2
16 p = 4 q = 0
80 p = 4 q = 1
400 p = 4 q = 2
32 p = 5 q = 0
160 p = 5 q = 1
64 p = 6 q = 0
320 p = 6 q = 1
128 p = 7 q = 0
256 p = 8 q = 0

它只是循环遍历 p 和 q 的每个组合，直到 n。

如果要排除 p = 0 和 q = 0，只需从 1 开始循环并设置 power2 = 2 和 power5 = 5。

Answer 3

您可能需要比 "generate all numbers and then test that they are 2^p 5^q" 更好的算法。但是要回答你如何确定一个正数是否为 2^p 5^q 的问题，你将所有可能的 2 和 5 分开。如果有任何遗漏，则原始数字没有那个因式分解：

while ( n % 5 == 0 ) {
    n /= 5;
}
while ( n % 2 == 0 ) {
    n /= 2;
}
return n==1;

有 faster 种方法可以测试数字是否为 2^p，但我发现它们的可读性不如最后四行。

确定可分解为 2^p5^q 的数字集的算法

Algorithm to determine set of numbers which can be factorised as 2^p5^q

algorithm

math

factorization