Commits

Shlomi Fish committed 77f8c60

Got rid of Math::GMP completely.

There should be a way to calculate it with 64-bit integers.

Comments (0)

Files changed (1)

project-euler/466/euler-466-experimental-with-modulo-bit-vec.pl

 use warnings;
 
 use integer;
-use Math::GMP ();
+# use Math::GMP ();
 
 use List::Util qw(first sum min);
 use List::MoreUtils qw(none);
 
 STDOUT->autoflush(1);
 
+sub gcd
+{
+    my ($n, $m) = @_;
+
+    if ($m > $n)
+    {
+        ($n, $m) = ($m, $n);
+    }
+
+    while ($m > 0)
+    {
+        ($n, $m) = ($m, $n%$m);
+    }
+
+    return $n;
+}
+
+sub lcm
+{
+    my ($n, $m) = @_;
+
+    return ($n * $m / gcd($n,$m));
+}
+
 my $DEBUG = 0;
 
 sub calc_P
 
         foreach my $next_row ($row_idx+1 .. $MIN)
         {
-            my $step = Math::GMP->new($row_idx)->blcm($next_row);
+            my $step = lcm($row_idx, $next_row);
             my $start_i_prod = $start_i * $row_idx;
             my $start_prod = ($start_i_prod / $step) * $step;
             if ($start_i_prod % $step)
 
             for my $maj_factor (reverse(2 .. $row_idx-1))
             {
-                $lcms[$maj_factor] = $lcms[$maj_factor+1]->blcm(
+                $lcms[$maj_factor] = lcm(
+                    $lcms[$maj_factor+1],
                     $maj_factor
                 );
             }
 my_test(11, 11, 53);
 my_test(12, 12, 59);
 my_test(12, 25, 143);
-# my_test(12, 345, 1998);
+my_test(12, 345, 1998);
 my_test(13, 13, 72);
 my_test(14, 14, 80);
 my_test(15, 20, 137);
-# my_test(16, 20, 142);
+my_test(16, 20, 142);
 }
 
-if (0)
+if (1)
 {
 my_test(64, 64, 1263);
 }