找到给出素数列表的因子的最接近的数字

Question

假设我有一个数字,我可以找到构成该数字的所有主要因素.例如,6000是2 ^ 4*3*5 ^ 3.

如果我有一个不能很好地分解的数字(给出一个可接受的素数列表),我怎样才能找到下一个最接近的数字？例如,给定数字5917,与素数列表2,3,5,7相关的最接近数字是多少？在这个例子中,这是6000.

我有一些蛮力找到答案的东西,但必须有一个更优雅的解决方案.

const UInt32 num = 5917;
const CVector<UInt32> primes = { 2, 3, 5, 7 };
const size_t size = primes.size();

UInt32 x = num;
while (x < num * 2)
{
    const UInt32 y = x;
    for(size_t i = 0; i < size && x > 1; ++i)
    {
        while(x % primes[i] == 0)
        {
            x /= primes[i];
        }
    }

    if (x == 1)
    {
        cout << "Found " << y << endl;
        break;
    }
    else
    {
        x = y + 1;
    }
}

编辑

我创建了一个使用蛮力方法和3个方法作为答案的测试,并得到了一些令人惊讶的结果.所有4个版本都会产生正确答案(感谢您的贡献),然而,蛮力方法似乎是最快的,数量级.我尝试了几个不同的系统,编译器和架构,它们都产生了大致一致的结果.

测试代码可以在这里找到:http://ideone.com/HAgDsF.请随时提出建议.

Answer 1

这个想法是，检查所有可能的可接受素数的乘积，并选择最好的。

To implement that, it's easiest, though probably not most efficient, to use recursion. Make a recursive function that "checks" a temporary product by adding all acceptable primes, one by one. To remember the best result, it's easiest to use a global variable.

int g_result;

void check(int num, int product, const vector<int>& primes)
{
    if (product >= num)
    {
        g_result = std::min(g_result, product);
    }
    else
    {
        for (int prime: primes)
            check(num, product * prime, primes);
    }
}

...
int main()
{
    g_result = INT_MAX;
    vector<int> primes = { 2, 3, 5, 7 };
    check(5917, 1, primes);
    std::cout << g_result;
}

The usage of a global variable is an ugly hack; it's good enough in this simple example, but not good for complicated (multi-threaded) systems. To eliminate the global variable, stuff the function into a class and make it a method; and use a member variable result instead of a global one.

Note: I used vector<int> instead of CVector<UInt32> for convenience.