c – 找到给定一个素数列表的最接近的数字

vector<int> primes = { 2,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作为列表中的最小素数.

>我的解决方案生成低于n的所有可能的值.旧值生成新值.每个值只能使用一次作为生成源.如果新值超过n,则被视为有效的候选者.如果列表将包含低于n的所有素数,则algo可以执行得很好.我不知道算法的漂亮的时间复杂度公式,但是低于n的有效候选人数乘以先前因子的对数.日志来自设置的数据结构操作.如果n可以小到足以分配大小为n的数组来标识已经生成的值,那么我们可以摆脱Log因子,一个简单的列表可以保存生成源值而不是set.
>您的初始解决方案有O(n(np logminP(n))).您检查每个数字是有效的,然后逐个从n到2n支付每个支票的np logminP(n).
> Recursive solution by @anatolyg在“访问”一些有效数字很多次,这是非常低效的有很大的缺陷.可以通过引入指示该号码已被“访问”的标志来修复.例如12 = 2 * 2 * 3将从6 = 2 * 3和4 = 2 * 2进行访问.次要缺陷是无数上下文切换,并支持每个呼叫的状态.该解决方案有一个全局变量,它将整个全局命名空间,这可以通过添加一个函数参数来解决.
> Solution by @dasblinkenlight缺乏效率,因为已经“使用”的候选人被用于生成已经存在于该集合中的数字的新候选者.虽然我已经借用了这个想法.

基于@גלעד ברקן’s answer,我创建了一个c解决方案,这似乎是渐近更有效率,因为没有对数因子.然而,我拒绝使用双对数和左整数解.这个想法很简单我们有一个低于num的产品列表.每个产品都是从第一个primesUsed素数生成的.然后,我们尝试使用下一个素材生成新产品.这种方法保证产生独特的产品：

vector<int> primes = { 2,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;

@L_450_51@