c++ - 找到最接近给定素数列表的因素的数字

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

我建议采用以下解决方案。我假设素数是从小到大排列的。我还使用了方便的 vector 和 int 类型。

vector<int> primes = { 2, 3, 5, 7 };
int num = 5917;
// initialize bestCandidate as a power of some prime greater than num
int bestCandidate = 1;
while (bestCandidate < num) bestCandidate *= primes[0];
set<int> s;
s.insert(1);
while (s.size()) {
    int current = *s.begin();
    s.erase(s.begin());
    for (auto p : primes) { // generate new candidates
        int newCandidate = current * p;
        if (newCandidate < num) {
            // new lower candidates should be stored.
            if (s.find(newCandidate) == s.end())
                s.insert(newCandidate);
        }
        else {
            if (newCandidate < bestCandidate) bestCandidate = newCandidate;
            break; // further iterations will generate only larger numbers
        }
    }
}
cout << bestCandidate;

Demo

接下来我想对建议的解决方案进行分析。让我用 np 作为素数； n 作为一个数字来找到最接近的结果； minP 作为列表中的最小素数。

1. 我的解决方案生成所有低于 n 的可能值。新值是从旧值中产生的。每个值仅一次用作生成源。如果新值超过 n，则它被视为有效候选值。如果列表包含所有小于 n 的素数，算法仍然可以执行良好。我不知道该算法的时间复杂度公式，但它是低于 n 的有效候选数乘以前一个因子的对数。日志来自set 数据结构操作。如果 n 可以足够小以分配大小为 n 的数组来标记哪些值已经生成，我们可以去掉对数因子，一个简单的列表可以保存生成源值的集合。

2. 您的初始解有 O(n(np + log_minP(n)))。您检查每个数字是否有效，然后从 n 到 2n 支付 np + log_minP(n) 每张支票。

3. Recursive solution by @anatolyg在多次“访问”某些有效数字方面存在很大缺陷，效率非常低。可以通过引入指示该号码已经“访问过”的标志来修复它。例如 12 = 2*2*3 将从 6 = 2*3 和 4 = 2*2 访问。次要缺陷是多次上下文切换和支持每次调用的状态。该解决方案有一个全局变量，使全局命名空间困惑，这可以通过添加函数参数来解决。

4. Solution by @dasblinkenlight缺乏效率，因为已经“使用过”的候选人被用来生成新的候选人，产生集合中已经存在的数字。虽然我借用了 set 的想法。

基于@גלעד ברקן's answer我创建了一个 c++ 解决方案，因为没有 log 因素，它确实似乎渐进地更有效。但是，我拒绝使用 double 对数，并使用整数解决方案。这个想法很简单。我们有一个低于 num 的产品列表。每个产品都是从第一个 primesUsed 素数生成的。然后我们尝试使用下一个素数生成新产品。这种方法保证生成独特产品:

vector<int> primes = { 2, 3, 5, 7, 11, 17, 23 };
int num = 100005917;
int bestCandidate = INT_MAX;
list<pair<int, int> > ls;
ls.push_back(make_pair(1, 0));
while (ls.size()) {
    long long currentProd = ls.front().first;
    int primesUsed = ls.front().second;
    ls.pop_front();
    int currentPrime = primes[primesUsed];
    while (currentProd < num) {
        if(primesUsed < primes.size() - 1)
            ls.push_back(make_pair(currentProd, primesUsed + 1));
        currentProd *= currentPrime;
    }
    bestCandidate = min((long long)bestCandidate, currentProd);
}
cout << bestCandidate;

Demo