[알고리즘] 14. N 값 이하의 서로소 개수 구하기

서로소 개수 구하기

• 특정 값 이하의 서로소의 개수를 구하시오.

문제 분석

• 오일러 피 함수 φ(n)=∣{m:1≤m≤n,gcd(mn)=1}∣

• φ(n)은 n과 서로소이고 n보다 작은 자연수의 개수

• 오일러 피 함수의 성질 1 : a, b가 서로소일 때, p(a)p(b) = p(ab)가 성립

• 오일러 피 함수의 성질 2 : 소수 p의 a제곱의 서로소 개수는 p의 a제곱 - p의 (a-1)제곱과 같음

코드 작성 - Sampling, Moduling

package algo;

public class Coprime01 {
    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 = 121;
        Uc f = new Uc();

        // 3. Moduling : 코드 간소화
        for (int i = 0; i < N; i++) {
            a++;
            if (f.gcd(a, N) == 1) {
                System.out.println(a + "는 서로소입니다.");
                count++;
            } else System.out.println(a + "는 서로소가 아닙니다.");
        }
        System.out.println(N + "의 서로소의 개수 : " + count);
        
        // QA : N = 121 (11^2)일 때, 서로소의 개수
        // 오일러 피 함수 공식 : p(11^2) = 11^2 - 11^1 = 121 - 11 = 110 (O)
    }
}

결과