Codility Java CommonPrimeDivisors

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
  public int solution(int[] A, int[] B) {
    int result = 0;
    for (int idx = 0; idx < A.length; idx++) {
      if (isSameDivisors(A[idx], B[idx])) {
        result++;
      }
    }
    return result;
  }
  // Check whether the sets of prime divisors of integers N and M are exactly the same.
  private boolean isSameDivisors(int num1, int num2) {
    int gcd = getGcd(num1, num2);
    return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2) == 1;
  }
  private int getDivisor(int gcd, int num) {
    int quotient = 0;
    while (quotient != 1) {
      quotient = getGcd(num, gcd);
      num /= quotient;
    }
    return num;
  }
  // Euclidean algorithm.
  private int getGcd(int num1, int num2) {
    if (num1 % num2 == 0) {
      return num2;
    } else {
      return getGcd(num2, num1 % num2);
    }
  }
}

설명

1. 유클리드 호제법¹을 사용하여 주어진 배열 A와 B 특정 idx에 속한 값의 최대 공약수를 구하여 변수 gcd로 임시 보관을 한다.
2. 구한 최대 공약수를 이용하여 배열 A와 B 특정 idx에 속한 값의 소인수가 각각 1인지를 확인하여 true면 소수 집합이 동일한 값의 개수를 저장하는 변수 result를 증가 시키고, 그렇지 않으면 다음 idx에 속한 값으로 넘어간다.
3. 반복이 끝나면 소수 집합이 동일한 값의 개수를 저장하는 변수 result를 주어진 문제의 결과로 반환한다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.

Reference

1. Wiki-Euclidean_Algorithm ↩