fork(1) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXSIZE = 1000000000;
  9.  
  10. map<int,unsigned char> m;
  11.  
  12. int count(int x, int level = 0, int curmin = MAXSIZE)
  13. {
  14.     if (level > curmin) return -1; // Отсечение - нет смысла лезть вглубь
  15.                                    // при наличии более короткого решения
  16.     if (x == 1) return 0;
  17.     if (m[x])
  18.     {
  19.         return m[x];               // Сохраненное значение
  20.     }
  21.     int res = MAXSIZE;
  22.     for(int i = sqrt(x)+0.1; i >= 1; --i)
  23.     {
  24.         if (x%i) continue;
  25.         int k = count(i+x/i-2, level+1, res);
  26.         if (k < 0) continue;
  27.         if (k < res) { res = k; }
  28.     }
  29.     return m[x] = res+1;
  30. };
  31.  
  32. int main(int argc, const char * argv[])
  33. {
  34.     int n = (argc > 1) ? atoi(argv[1]) : MAXSIZE;
  35.     if (n > MAXSIZE) n = MAXSIZE;
  36.     cout << n << ":  " << count(n) << endl;
  37.  
  38.     int cur = m[n];
  39.     while (n > 1)
  40.     {
  41.         for(int i = 1; i*i <= n; ++i)
  42.         {
  43.             if (n%i) continue;
  44.             if (m[i+n/i-2] == cur-1)
  45.             {
  46.                 n = i+n/i-2;
  47.                 --cur;
  48.                 cout << i << " ";
  49.                 break;
  50.             }
  51.         }
  52.     }
  53.     cout << endl;
  54. }
Success #stdin #stdout 0.12s 5180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000:  8
250 504 87 13 5 2 2 1
https://ideone.com/UayUDV
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!