project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_95.cpp (1424B)

      1 #include "Euler.h"
      2 
      3 int Euler::AmicableChains()
      4 {
      5     int one_million = 1000000;
      6     int longest = 0, solution = 0;
      7     double root = floor(sqrt(one_million)) + 1;
      8 
      9     std::vector<int> divisors(one_million + 1, 1);
     10 
     11     for (int i = 2; i < root; ++i) {
     12         for (int j = 2; i * j <= one_million; ++j) {
     13             divisors[i * j] += i + ((j >= root) ? j : 0);
     14         }
     15     }
     16 
     17     for (int n = 1; n <= one_million; ++n) {
     18         int length = 0;
     19         int candidate = one_million;
     20         int slow_ptr = n, fast_ptr = n;
     21         bool loop_found = false;
     22 
     23         while(fast_ptr > 1 && slow_ptr <= one_million && fast_ptr <= one_million) {
     24             length += loop_found;
     25             fast_ptr = divisors[fast_ptr];
     26 
     27             if (fast_ptr <= 1 || fast_ptr > one_million) {
     28                 break;
     29             }
     30 
     31             if (loop_found && slow_ptr < candidate) {
     32                 candidate = slow_ptr;
     33             }
     34 
     35             if (slow_ptr == fast_ptr) {
     36                 if (loop_found) {
     37                     if (length > longest) {
     38                         solution = candidate;
     39                         longest = length;
     40                     }
     41 
     42                     divisors[candidate] = 1;
     43                     break;
     44                 }
     45 
     46                 loop_found = true;
     47             }
     48 
     49             slow_ptr = divisors[slow_ptr];
     50             fast_ptr = divisors[fast_ptr];
     51         }
     52     }
     53 
     54     return solution;
     55 }