Commits

Shlomi Fish  committed 9ed29c7

More optimisations.

  • Participants
  • Parent commits 0f98af9

Comments (0)

Files changed (1)

File project-euler/127/euler-127.pl

 
 my %C_s = ();
 
+my %C_blacklist = ();
+
 B_loop:
 for my $B (3 .. 1_000-1)
 {
         if (gcd($B, $A) == 1)
         {
             my $C = $A + $B;
-            if (gcd($C, $A) == 1 and gcd($C, $B) == 1 and 
-                radical($A*$B*$C) < $C)
+
+            if (!exists($C_blacklist{$C}))
             {
-                print "Found $C\n";
-                $C_s{$C} = 1;
+                my $rad_C = radical($C);
+
+                if ($rad_C * 6 >= $C)
+                {
+                    $C_blacklist{$C} = 1;
+                }
+                # Since gcd(A,B) = 1 then gcd(A+B,A) and gcd(A+B,B) must be one
+                # as well.
+                elsif ( # gcd($C, $A) == 1 and gcd($C, $B) == 1 and 
+                    radical($A*$B*$C) < $C)
+                {
+                    print "Found $C\n";
+                    $C_s{$C} = $C_blacklist{$C} = 1;
+                }
             }
         }
     }