Check whether two numbers have the same prime divisors.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/12-euclidean_algorithm/common_prime_divisors/
- Time Complexity:
Solution:
Solution to Codility's Common Prime Divisors problem which is from the Codility Lesson 12: Euclidean algorithm and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to check whether two numbers have the same prime divisors. You can find the question of this CommonPrimeDivisors problem in the Codility website.
package Codility.Lesson12;
import java.util.*;
public class CommonPrimeDivisors {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 15, 10, 9 };
int[] a2 = { 75, 30, 5 };
int result2 = solution(a1, a2);
System.out.println(result2);
}
public static int solution(int[] A, int[] B) {
int count = 0;
for(int i=0;i<A.length;i++) {
if(hasSamePrimeDivisors(A[i], B[i])){
count++;
}
}
return count;
}
public static int gcd(int a, int b) {
if(a % b == 0) return b;
return gcd(b,a%b);
}
public static boolean hasSamePrimeDivisors(int a, int b) {
int gcdValue = gcd(a,b);
int gcdA;
int gcdB;
while(a!=1) {
gcdA = gcd(a,gcdValue);
if(gcdA==1)
break;
a = a/gcdA;
}
if(a!=1) {
return false;
}
while(b!=1) {
gcdB = gcd(b,gcdValue);
if(gcdB==1)
break;
b = b/gcdB;
}
return b==1;
}
}