Pythagorean triples/Java/Brute force primitives: Difference between revisions

This version brute forces primitive triple candidates and then scales them to find the rest (under the perimeter limit of course). Since it only finds the primitives mathematically it can optimize its candidates based on some of the properties [[wp:Pythagorean_triple#Elementary_properties_of_primitive_Pythagorean_triples|here]] -- namely that a and b have opposite evenness, only one of a and b is divisible by 3, only one of a and b is divisible by 4, c is always odd, and that a² + b² must be a perfect square (which [[wp:Square_number#Properties|don't ever end in 2, 3, 7, or 8]]). NotablyAfter using those rules to eliminate candidates for a,b pairs, it doesn'tchecks usethat a GCDand functionb toare checkcoprime. forSince primitivesmany (<code>BigInteger.gcd()</code>a,b usespair thecandidates binaryhave GCDalready algorithmbeen eliminated, [[wp:Computational_complexity_of_mathematical_operations#Number_theory|whichthis ischeck O(n²)]])actually speeds things up a little bit by letting the program skip some c loops. For a perimeter limit of 1000, it is about 5 times faster than [[Pythagorean triples#Java|the other brute force version]]. For a perimeter limit of 10000, it is about 1517 times faster. It also does not mark the primitives.

It defines a <code>Triple</code> class which is comparable so it can be placed in a <code>SetTreeSet</code> for easy sorting and to remove duplicates (e.g.the thisGCD algorithmcheck findsshould [15,remove 20duplicates, 25] as a primitive candidate afterbut it's hadnice alreadyto been added by scaling [3, 4,make 5]sure). It also can scale itself by an integer factor.

public class PythTrip2PythTrip{