如果我有一个数字不能很好地分解(给定一个可接受的素数列表),我该如何找到下一个最接近的数字？例如,给定数字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> 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;
接下来我想对提出的解决方案进行分析.让我用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;
