[프로그래머스] Level0.유한소수 판별하기

내 풀이

class Solution {
static int[] num;
static int n;
    public int solution(int a, int b) {
        int answer = 1;
        int gcd = GCD(a,b);
        b = b/gcd;
        EulerPhi(b);
        for(int i=2; i<=b; i++) {
            if(num[i] != 0) {
                if((i != 2 && i != 5) && b%i==0) {
                    answer=2;
                    break;
                }
            }
        }
        return answer;
    }
    
    public int GCD(int a, int b) {
        int gcd = 1;
        for(int i=1; i<=a && i<=b; i++) {
            if(a%i==0 && b%i==0) gcd = i;
        }
        return gcd;
    }
    public void EulerPhi(int n) {
        num = new int[n+1];
        for(int i=2; i<=n; i++) {
            num[i] = i;
        }
        for(int i=2; i<=n; i++) {
            for(int j=i+i; j<=n; j +=i) {
                if(num[j] != 0) num[j] =0;
            }
        }
    }
}

gcd구하는것까지는 좋았으나 오일러피사용해서 1~n사이의 소수를 구한 후, 해당 소수로 다 나누어보는로직은 비효율적이라는생각이들어 다른 풀이로 공부한다.

다른 풀이

class Solution {
    public int solution(int a, int b) {
        b /= gcd(a, b);
        while (b != 1) {
            if (b % 5 == 0) {
                b /= 5;
                continue;
            }
            if (b % 2 == 0) {
                b /= 2;
                continue;
            }
            return 2;
        }
        return 1;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

• 우선 gcd를 구해서 진행하는건 동일하다(gcd의 로직은 동일하지않음. 유클리드 호제법으로 진행할 것)
• 기약분수가 되면, 분모를 5와 2로 각각 나눠지지않을때까지 계속 나누어준다.
• 다 나누었는데도 b가 1이 아니면 무한소수이고, 2와 5로 나눌수없을때까지 나누었을때 b가 1이되면 유한소수인것이다.

알게된 점

• 유한소수의 조건 : 기약분수로 나타냈을 때, 분모의 소인수가 2와 5만 존재해야한다.(즉 기약분수의 분모는 2와 5로 나눌 수 있을만큼 나누었을 때, 더이상 인수가 없어서 1이되어야한다)