project-euler

commit 644a8c74c30a358d8b91711d990a69c5364eff6b
parent 0a6a0bf18de14194c429e70adc682d221ac19f0c
Author: mpizzzle <m@michaelpercival.xyz>
Date:   Sun, 27 Sep 2020 22:11:22 +0100

looked up the proper algo for calculating divisors, massive time improvement

Diffstat:
M
Euler_95.cpp
 | 
44
++++++++++++++------------------------------

1 file changed, 14 insertions(+), 30 deletions(-)
diff --git a/Euler_95.cpp b/Euler_95.cpp
@@ -1,47 +1,32 @@
 #include "Euler.h"
 
-int sumProperDivisors(int n)
-{
-    int sum = 0;
-
-    for(int k = 1; k <= n / 2; ++k)
-    {
-        if(n % k == 0)
-        {
-            sum += k;
-        }
-    }
-
-    return sum;
-}
-
 int Euler::AmicableChains()
 {
     int one_million = 1000000;
     int longest = 0;
     int solution = 0;
+    double root = floor(sqrt(one_million)) + 1;
 
-    std::vector<int> cache(one_million + 1, 0);
+    std::vector<int> divisors(one_million + 1, 1);
 
-    for (int i = 0; i <= one_million; ++i) {
-        cache[i] = sumProperDivisors(i);
-        std::cout << i << std::endl;
+    for (int i = 2; i < root; ++i) {
+        for (int j = 2; i * j <= one_million; ++j) {
+            divisors[i * j] += i + ((j >= root) ? j : 0);
+	}
     }
 
-    std::cout << std::endl << "precalc done." << std::endl;
+    //std::cout << std::endl << "precalc done." << std::endl;
 
     for (int n = 1; n <= one_million; ++n) {
         int length = 0;
         int candidate = one_million;
         int slow_ptr = n;
         int fast_ptr = n;
-        std::cout << n << ": ";
 
         while(true) {
-            fast_ptr = cache[fast_ptr];
+            fast_ptr = divisors[fast_ptr];
 
             if (fast_ptr <= 1 || fast_ptr > one_million) {
-                std::cout << "no bueno." << std::endl;
                 break;
             }
 
@@ -49,7 +34,7 @@ int Euler::AmicableChains()
                 while (true) {
                     std::cout << slow_ptr << " -> ";
                     length++;
-                    fast_ptr = cache[fast_ptr];
+                    fast_ptr = divisors[fast_ptr];
 
                     if (slow_ptr < candidate) {
                         candidate = slow_ptr;
@@ -67,22 +52,21 @@ int Euler::AmicableChains()
                             std::cout << "not a winner." << std::endl;
                         }
 
-                        cache[solution] = 0;
+			divisors[candidate] = 1;
                         break;
                     }
 
-                    slow_ptr = cache[slow_ptr];
-                    fast_ptr = cache[fast_ptr];
+                    slow_ptr = divisors[slow_ptr];
+                    fast_ptr = divisors[fast_ptr];
                 }
 
                 break;
             }
 
-            slow_ptr = cache[slow_ptr];
-            fast_ptr = cache[fast_ptr];
+            slow_ptr = divisors[slow_ptr];
+            fast_ptr = divisors[fast_ptr];
 
             if (fast_ptr <= 1 || slow_ptr > one_million || fast_ptr > one_million) {
-                std::cout << "no bueno." << std::endl;
                 break;
             }
         }