I am new to coding. Given int arrays A and B, I would like to find the maximum GCD (Greatest Common divisor) any element of A and any element of B. I am doing the following
- Sorting both arrays, then
- Comparing every value of array A to array B to find GCD
- Using a temp number I am checking if the GCD found is bigger than previous.
- Finally returning the value (i.e. temp)
The GCD(a,b) returns the Greatest Common divisor of a and b.
Note: I am not comparing elements of A array with A.
Is there any way to improve the performance of my Code?
I want to decrease the time for a large number of inputs of Arrays A and B in the for loops by applying some Conditions.
Example :
A=2,5,8,9
B=4,12,8,7,16
Now if we choose 8 from A and 8 from B we get maximum GCD i.e. 8 . And then returning The maximum GCD (i.e. 8 in my example).
private static int GCD(int a, int b) {
BigInteger b1 = BigInteger.valueOf(a);
BigInteger b2 = BigInteger.valueOf(b);
BigInteger gcd = b1.gcd(b2);
return gcd.intValue();
}
public static int maximumGcd(int[] A, int[] B) {
Arrays.sort(A);
Arrays.sort(B);
int temp = 0;
for (int i = A.length-1; i >0; i--) {
for (int j = A.length-1; j >0; j--) {
int tempGcd = GCD(A[i],B[j]);
if ( tempGcd > temp){
temp = tempGcd;
}
}
}
return temp;
}