有没有一种算法可以找到最接近的仅由小因子组成的数？

Question

我需要进行一些实时 DFT，而我使用的算法在样本数量可以被分解成小因子时效率最高。

假设我有一个数字 n 和因子 2、3、5。如何找到最接近（与 n 相比）的数字，其质因数分解中只包含2、3、5这些数字？

n 几乎总是小于 50,000，所以暴力枚举可能是一个不错的选择。

- Henricus V.

---

那听起来更像是一个适合http://math.stackexchange.com/网站的问题。 - trincot

你可以使用类似筛子的方法。 - Rafaf Tahsin

通常 n 的大小是多少？如果它被限制在32位内，最有效的解决方案可能是预先计算所有候选数字，将它们存储在一个数组中，然后进行二分查找。 - Roland Illig

你对一个整洁、快速的算法感兴趣吗，用于查找最接近的只有2个因子（比如2和3）的更大数字？ - j_random_hacker

@j_random_hacker 我认为那会起作用。 - Henricus V.

由于您的范围，您可以预先计算所有可能的值，然后对每个样本在表格上进行二分查找。 - 500 - Internal Server Error

Answer 1

在1到50000范围内，只有265个数字可以被2、3、5整除。因此，你可以制作一个小表格，在表格中查找答案。但是，在我的计算机上，平均需要6.5微秒来查找给定数字的最近的2-3-5可整除数，所以我会说暴力破解已经足够好了。

int isValid( int n )
{
    while ( n%2 == 0 )
        n /= 2;
    while ( n%3 == 0 )
        n /= 3;
    while ( n%5 == 0 )
        n /= 5;

    return n == 1;
}

int findBest( int n )
{
    for ( int i = 0; i < n; i++ )
    {
        if ( isValid(n+i) )
            return n+i;
        if ( isValid(n-i) )
            return n-i;
    }
    return 0;   // should never get here
}

int main( void )
{
    for ( int n = 1; n <= 50000; n++ )
        printf( "%d->%d\n", n,findBest(n) );
}

- user3386109

Answer 2

一种快速的因数对算法

虽然这并没有完全解决问题，即给定一个整数x，它只能找到最接近大于或等于x的没有除了2和3之外的因数（或任何其他给定的因数对）。但是我认为这很巧妙，由于它在O（log x）时间和O（1）空间中运行，因此它可能是有用的！ 它的概念类似于Bresenham线算法。 伪代码如下：

1. 从b = y = 2 ^ RoundUp（log2（x））开始，这确保了b = y>= x。
2. 如果y < x，则将y设置为y * 3并转到步骤2。
3. 如果y < b，则设置b = y。 （b记录迄今为止的最佳候选者。）
4. 如果y是奇数，则停止并返回b。
5. 否则，将y = y / 2，并进入步骤2。

正确性

为什么这有效呢？请注意，始终有y = 2 ^ i * 3 ^ j，其中i，j >= 0，而且随着时间的推移，i只会减少，而j只会增加。我们在步骤2进入时保持的不变量是“任何值z = 2 ^ a * 3 ^ b，其中a> i或b < j已知为不相关的”（即无效或没有比某个已发现的解决方案更好），因此不需要考虑。 ”这显然在第一次到达步骤2时是正确的，因为y是2的幂并且已经>= x，因此任何具有a > i的2 ^ a * 3 ^ b会是至少2 * y（无论b如何）这比y更差；而且没有整数z可以具有y中少于j = 0个3的幂。

（表达这种不变性的另一种方法是“要么我们已经找到了最优解，要么它就是一些数字z = 2 ^ a * 3 ^ b，其中a <= i且b >= j .“）

如果在第2步中满足条件“y < x”，那么y = 2^i*3^j不是一个有效的解，因为它太低了。更强烈地说，对于任何a <= i，2^a*3^j也不能是有效的解，因为任何这样的解都至少与y一样低。因此，现在我们知道（从不变量中得知）任何满足（a > i OR b < j）的一对（a，b）都是无趣的，并且我们从刚刚成功的“y < x”测试中得知，任何满足（a <= i AND b = j）的一对（a，b）也是无趣的。现在考虑任何满足稍微不同条件（a > i OR b < j+1）的一对（a，b）：如果（a，b）不满足无趣性的第一个条件（来自不变量），则我们有((a > i OR b < j+1) AND !(a > i OR b < j))，这通过德摩根定律简化为(b < j+1 AND a <= i AND b >= j)（因为使(a <= i AND b >= j)成立需要(a <= i)为真，强制(a > i)为假，从而允许将其从OR中消除），这显然与（a <= i AND b = j）相同--但这正是我们通过“y < x”测试的成功刚刚建立第二种无趣性的条件。因此，这证明了任何满足（a > i OR b < j+1）的一对（a，b）都是无趣的--这在增加j后恰好变成我们想要保持的不变量。

步骤5中减少i的理由几乎是相同的，但是相反的，所以我不会详细说明它。略微不同之处在于，如果我们到达步骤5，那么我们没有一个无效解，而是有一个至少与b中最佳解一样高的解（请注意，如果必要，我们已更新b，以便这仍然成立），因此它和每个更高的解（从此时起）对我们来说都是无趣的。

算法生成的每个y值都具有比先前生成的任何值少一个因子2或多一个因子3，因此很明显所有生成的y值都是不同的。早期段落中的推理建立了只有被证明为无趣的y值不被生成。因此，如果算法总是在有限时间内停止，则它是正确的。下一节将暗示这确实是正确的。

运行时间

第五步（将i减1的效果）最多只会执行log2(x)+1次，因为i的起始值不超过这个值，没有其他东西会影响i，在i达到0时，y将是奇数，导致第四步终止函数。但是第二步中增加j的条件可以触发多少次呢？

最初y >= x，因此需要执行第5步才能满足第2步触发的y < x条件。但是，一旦通过第5步的某次执行实现了y < x，它就会在下一次第2步的执行中立即撤消：这是因为为了执行第5步，我们必须有y >= x，如果我们在那个第5步中将y除以2，然后在下一个第2步中将其乘以3，它将必然至少与之前一样大，暗示着y >= x，进而意味着step 2将永远不会连续两次触发而没有在中间执行step 5。因此，step 2最多会触发与step 5相同的次数，即最多log2(x)+1次。这将把算法的整体运行时间限制在O(log x)。

注： - 您可以通过将第1步中的log2()替换为一个循环来避免浮点运算，该循环从1开始，不断加倍，直到大于等于x。这是O(log x)，因此不会影响时间复杂度。 - 您可以使用任何其他一对因数。唯一的真正变化是，如果f是代码中“替换”2的因数，则第4步应在y % f != 0时停止。

- j_random_hacker

---

关于注释1：在某些CPU架构上，有一些特殊的指令可以在O(1)时间内完成此操作。GCC提供了一组内置函数__builtin_clz{,l,ll}来以与CPU无关的方式完成此操作。 - Ruslan

Answer 3

我不确定是否有任何高效的解决方案。以下是寻找最接近n的数字的暴力方法。

    int diff=Integer.MAX_VALUE;
    int num=0;
    public void closestNumber(int n,int curr)
    {
        if(diff < Math.abs(n -curr) && curr  >= n)
        return;
        if(diff >= Math.abs(n -curr))
        {
            diff = Math.abs(n -curr);
            num=curr;
        }
        closestNumber(n,curr*2);
        closestNumber(n,curr*3);
        closestNumber(n,curr*5);

    }


closestNumber(n,1);

System.out.println("closest number: "+num);

- Sandeep Reddy Goli

---

sum 没有解释。 - Rafaf Tahsin

Answer 4

编辑：

以下代码找到离目标最近的可被给定因数集中至少一个数整除的数字。它不能解决明确的目标，即找到仅能被给定因数集整除的最近数字。

原文：

可被2、3或5整除的数字系列是 OEIS A080671，并且具有简单的递归公式a(n+22) = a(n)+30。此外，该系列方便地仅具有单整数间隔。这意味着您只需确定您的数字是否位于其中一个间隔上，并选择下一个或前一个整数。

class NumberFinder
{
public:
    NumberFinder()
    {
        for (int i = 0; i < 2 * 3 * 5; i++)
        {
            bool hasSmallFactors =
                (i % 2 == 0) ||
                (i % 3 == 0) ||
                (i % 5 == 0);
            series.push_back(hasSmallFactors);
        }
    }

    int Find(int n)
    {
        int x = n % (2 * 3 * 5);
        if (series[x]) return n; // already good
        return n + 1; // guaranteed to be good
    }

private:
    vector<bool> series;
};

这也可以推广到任何一组所需的因素：

class NumberFinder
{
public:
    NumberFinder(vector<int> factors)
    {
        product = 1;
        for (auto factor : factors) product *= factor;
        for (int i = 0; i < product; i++)
        {
            bool hasSmallFactors = false;
            for (auto factor : factors)
            {
                if (i % factor == 0) hasSmallFactors = true;
            }
            series.push_back(hasSmallFactors);
        }
    }

    int Find(int n)
    {
        int lo = n;
        int hi = n;
        bool found = series[n % product];
        while (!found)
        {
            if (--lo < 0) lo = 0;
            hi++;
            found = series[hi % product] || series[lo % product];
        }
        if (series[lo % product]) return lo;
        return hi;
    }

private:
    int product;
    vector<bool> series;
};

- MooseBoys

---

我正在尝试寻找仅可被2、3、5及其乘积整除的数字。OEIS A080671包含不满足此条件的数字，例如21。 - Henricus V.

@HenryW。这是一个明显更简单的问题。如果你的数字必须能被2、3和5整除，那么你只需要找到最接近235=30的倍数的匹配项，即((n+15)/30)*30，或者更一般地说，((n+(p/2))/p)*p)，其中p是你的目标因子的乘积。 - MooseBoys

抱歉，我的意思是得到的数字的质因数分解中不能有除了“2、3、5”以外的任何数字。 - Henricus V.

@HenryW。啊，这是一个相当困难的问题（寻找最接近的汉明数），不能像上面所示使用周期性序列来解决。 - MooseBoys