algorithm - 有没有一种算法可以找到最近的只有小因子的数字？

Question

我需要做一些实时 DFT，当样本数量可以分解成小因子时，我使用的算法是最有效的。

假设我有一个数字 n 和因子 2, 3, 5。如何找到最接近的数字(与 n 相比)，其质因数分解不包含除 2,3,5 以外的数字？

n 几乎总是低于 50,000，因此暴力破解可能是个好主意。

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) );
}