fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXSIZE = 1000000000;
  8.  
  9. unsigned char m[MAXSIZE+1];
  10.  
  11. int count(int x, int level = 0, int curmin = MAXSIZE)
  12. {
  13.     if (level > curmin) return -1;
  14.     if (x == 1) return 0;
  15.     if (m[x])
  16.     {
  17.         return m[x];
  18.     }
  19.     int res = MAXSIZE;
  20.     for(int i = sqrt(x)+0.1; i >= 1; --i)
  21.     {
  22.         if (x%i) continue;
  23.         int k = count(i+x/i-2, level+1, res);
  24.         if (k < 0) continue;
  25.         if (k < res) { res = k; }
  26.     }
  27.     return m[x] = res+1;
  28. };
  29.  
  30. int main(int argc, const char * argv[])
  31. {
  32.     int n = (argc > 1) ? atoi(argv[1]) : MAXSIZE;
  33.     if (n > MAXSIZE) n = MAXSIZE;
  34.     cout << n << ":  " << count(n) << endl;
  35.  
  36.     int cur = m[n];
  37.     while (n > 1)
  38.     {
  39.         for(int i = 1; i*i <= n; ++i)
  40.         {
  41.             if (n%i) continue;
  42.             if (m[i+n/i-2] == cur-1)
  43.             {
  44.                 n = i+n/i-2;
  45.                 --cur;
  46.                 cout << i << " ";
  47.                 break;
  48.             }
  49.         }
  50.     }
  51.     cout << endl;
  52. }
  53.  
  54.  
Success #stdin #stdout 0.04s 992768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000:  8
250 504 87 13 5 2 2 1
https://ideone.com/ZXbid7
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!