[알고리즘] 15. N 값 이하의 서로소 값 찾기

서로소 값 찾기

• N 값 이하의 서로소의 값을 찾으시오.

문제 분석

• GCD(a, b) = 1인 값

• 소수끼리는 GCD = 1

• 그 외의 약수가 겹치지 않는 수를 어떻게 찾을까?

코드 작성 - Sampling, Modeling

package algo;

public class Coprime02 {
    public static void main(String[] args) {
        // 1. Sampling : 10 이하의 서로소를 찾으시오.
        // 2. Hard Coding : 특징 찾기 1 - 10의 서로소 : 1, 3, 7, 9 - 4개
        // 2. Hard Coding : 특징 찾기 2 - N이 짝수면, 2의 배수는 전부 서로소가 되지 못함
        // 2. Hard Coding : 특징 찾기 3 - N-1은 무조건 서로소 (10과 9는 서로소)
        // 2. Hard Coding : 특징 찾기 4 - N이 소수면, 나머지 수들은 전부 서로소 (소수는 약수를 1과 자신밖에 가지지 않음)
        // 2. Hard Coding : 특징 찾기 5 - N이 소수의 거듭제곱이면, 그 소수를 제외한 나머지 수들은 전부 서로소
        // 2. Hard Coding : 특징 찾기 6 - 오일러 피 함수 1 : 서로소인 a, b에 대하여 p(a*b) = p(a)*p(b)
        // 2. Hard Coding : 특징 찾기 7 - 오일러 피 함수 2 : p(n^a) = n^a - n^a-1
        // 2. Hard Coding : 특징 찾기 8 - N과 특정 수(a)의 최대 공약수가 1이면 서로소
        int a = 0, count = 0;
        final int N = 49;
        Uc f = new Uc();

        // 3. Moduling : 코드 간소화
        System.out.print(N + "의 서로소 : ");
        for (int i = 0; i < N; i++) {
            a++;
            if (f.gcd(a, N) == 1) {
                System.out.println(a + " ");
                count++;
            }
        }
    }
}

결과