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

前端之家收集整理的这篇文章主要介绍了c – 找到给定一个素数列表的最接近的数字前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
说我有一个数字,我可以找到构成这个数字的所有主要因素.例如,6000是2 ^ 4 * 3 * 5 ^ 3.

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

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

const UInt32 num = 5917;
const CVector<UInt32> primes = { 2,3,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.请随时提出建议.

解决方法

我建议以下解决方案.我假设素数从低到高排序.我也使用了方便的vector和int类型.
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;

Demo

原文链接:https://www.f2er.com/c/113460.html

猜你在找的C&C++相关文章