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

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

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

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

  1. const UInt32 num = 5917;
  2. const CVector<UInt32> primes = { 2,3,7 };
  3. const size_t size = primes.size();
  4.  
  5. UInt32 x = num;
  6. while (x < num * 2)
  7. {
  8. const UInt32 y = x;
  9. for(size_t i = 0; i < size && x > 1; ++i)
  10. {
  11. while(x % primes[i] == 0)
  12. {
  13. x /= primes[i];
  14. }
  15. }
  16.  
  17. if (x == 1)
  18. {
  19. cout << "Found " << y << endl;
  20. break;
  21. }
  22. else
  23. {
  24. x = y + 1;
  25. }
  26. }

编辑

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

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

解决方法

我建议以下解决方案.我假设素数从低到高排序.我也使用了方便的vector和int类型.
  1. vector<int> primes = { 2,7 };
  2. int num = 5917;
  3. // initialize bestCandidate as a power of some prime greater than num
  4. int bestCandidate = 1;
  5. while (bestCandidate < num) bestCandidate *= primes[0];
  6. set<int> s;
  7. s.insert(1);
  8. while (s.size()) {
  9. int current = *s.begin();
  10. s.erase(s.begin());
  11. for (auto p : primes) { // generate new candidates
  12. int newCandidate = current * p;
  13. if (newCandidate < num) {
  14. // new lower candidates should be stored.
  15. if (s.find(newCandidate) == s.end())
  16. s.insert(newCandidate);
  17. }
  18. else {
  19. if (newCandidate < bestCandidate) bestCandidate = newCandidate;
  20. break; // further iterations will generate only larger numbers
  21. }
  22. }
  23. }
  24. 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素数生成的.然后,我们尝试使用下一个素材生成新产品.这种方法保证产生独特的产品:

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

Demo

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