A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A primitive Pythagorean triple is one in which a, b and c are coprime. A right triangle whose sides form a Pythagorean triple is called a Pythagorean triangle.
Finding all the triplets for c2<= n :
public class PythagoreanTriplet {
static int count = 0;
public static void main(String[] args) {
Long start = System.currentTimeMillis();
//time comparison for various number of inputs
//int n = 100000000;//total time in ms=1118847
//int n = 10000000;//total time in ms=36031
//int n = 1000000;//total time in ms=2122
//int n = 100000;//total time in ms=66
//int n = 10000;//total time in ms=20
//int n = 1000;//total time in ms=2
//int n = 100;//total time in ms=1
int n = 1000;
List<Integer> listOfSquraes = new ArrayList<>();
for (int i = 1;; i++) {
int sqr = i*i;
if(sqr > n){
break;
} else {
listOfSquraes.add(sqr);
}
}
int k =listOfSquraes.size();
for (int i = 0; i<k; i++) {
findPythagoreanTriplet(listOfSquraes.get(i), listOfSquraes,k);
}
Long end = System.currentTimeMillis();
System.out.println("total triplets found=" + count + " and total time in ms=" + (end-start));
}
public static void findPythagoreanTriplet(int sumRequired,List<Integer> list, int size){
for (int i = 1; i < size; i++) {
for (int j = i+1; j < size; j++) {
int sum = list.get(i) + list.get(j);
int diff = sumRequired-sum;
if(diff == 0){
count++;
System.out.println("("+(int)Math.sqrt(list.get(i)) + "," + (int)Math.sqrt(list.get(j)) + "," + (int)Math.sqrt(sumRequired)+")");
}
}
}
}
}
Output :
(3,4,5)
(6,8,10)
(5,12,13)
(9,12,15)
(8,15,17)
(12,16,20)
(7,24,25)
(15,20,25)
(10,24,26)
(20,21,29)
(18,24,30)
total triplets found=11 and total time in ms=2
Time complexity though O(n3) which we can reduce with the improving the search to O(nlogn) , so overall complexity would reduce to O(n2logn).
