[JAVA] 8. 필수 알고리즘 Ⅵ. 서로소

❗

오일러 피함수

x와 서로소이고 x보다 작은 자연수(음이 아닌 정수)의 개수

예를 들어 Φ(100)은 다음과 같이 구할 수 있다. 100의 소인수는 2와 5이므로, 아래 공식이 성립한다.

1. 전체탐색으로 서로소 개수 구하기

1. N이 12라면

• 1부터 12까지 모든 수를 12와 최대공약수를 비교해 1이면 서로소

package algo;

public class Coprime03 {

    static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int num = 12;
        int n = 0;

        // 전체탐색으로 num이하의 서로소 찾기
        // 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다

        // 1일 경우
        // 1은 모든 수와 최대 공약수가 1로 같다.

        // 2일 경우
        n = 2;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 3일 경우
        n = 3;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 4일 경우
        n = 4;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 5일 경우
        n = 5;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
    }
}

2. 공통모듈로 만들자

package algo;

public class Coprime03 {

    static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int num = 12;
        int n = 1;

        // 전체탐색으로 num이하의 서로소 찾기
        // 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다

        // 1일 경우
        // 1은 모든 수와 최대 공약수가 1로 같다.

        // 2일 경우
        n++;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 3일 경우
        n++;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 4일 경우
        n++;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);

        // 5일 경우
        n++;
        System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
    }
}

3. 반복문으로 N숫자(12)까지 반복해 보자

package algo;

public class Coprime03 {

    static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int num = 12;
        int n = 1;

        // 전체탐색으로 num이하의 서로소 찾기
        // 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다

        // 1일 경우
        // 1은 모든 수와 최대 공약수가 1로 같다.
        // 1은 모든 수와 서로소다

        // 12-1번 반복
        for (int i = 0; i < num - 1; i++) {
            n++;
            System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
        }
    }
}

4. 서로소의 개수를 구해보자

package algo;

public class Coprime03 {

    static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int num = 12;
        int n = 1;
        int count = 1;

        // 전체탐색으로 num이하의 서로소 찾기
        // 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다

        // 1일 경우
        // 1은 모든 수와 최대 공약수가 1로 같다.
        // 1은 모든 수와 서로소다

        // 12-1번 반복
        for (int i = 0; i < num - 1; i++) {
            n++;
            if (gcd(num, n) == 1) {
                count++;
                System.out.println(n + "은 서로소다");
            } else {
                System.out.println(n);
            }
        }
        System.out.println(count + "개");
    }
}

2. 오일러 피함수로 서로소 개수 구하기

1. N의 값이 12라면, 12의 약수를 구한다.

• 12약수는 1~12까지의 수 중 12%n==0을 성립하는 n이다.

• 1, 2, 3, 4, 6, 12

package algo;

import java.util.ArrayList;
import java.util.List;

public class Coprime04 {
    public static void main(String[] args) {
        // 숫자 1은 제외한다.
        // 1. 12의 약수 구하기
        List<Integer> list = new ArrayList();
        int n = 12;
        for (int i = 2; i <= n; i++) {
            if (12 % i == 0) {
                list.add(i);
            }
        }
        System.out.println("1을 제외한 12의 약수들");
        System.out.println(list);

    }
}

2. 각 약수들이 소수인지 판별

• 약수의 개수가 2개면 소수, 1과 자기자신

package algo;

import java.util.ArrayList;
import java.util.List;

public class Coprime04 {
    public static void main(String[] args) {
        // 숫자 1은 제외한다.
        // 1. 12의 약수 구하기
        List<Integer> list = new ArrayList();
        int n = 12;
        for (int i = 2; i <= n; i++) {
            if (12 % i == 0) {
                list.add(i);
            }
        }
        
				// 2. 약수가 소수인지 확인하기
        for (int number : list) {
            int count = 0;
            for (int i = 1; i <= number; i++) {
                if (number % i == 0) {
                    count++;
                }
            }
            if (count == 2) {
                System.out.println(number + "는 소수다");
            }
        }
    }
}

3. 오일러 피함수 공식 사용

package algo;

import java.util.ArrayList;
import java.util.List;

public class Coprime04 {
    public static void main(String[] args) {
        // 숫자 1은 제외한다.
        // 1. 12의 약수 구하기
        List<Integer> list = new ArrayList();
        int n = 12;
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                list.add(i);
            }
        }

        // 2. 약수가 소수인지 확인하기
        List<Integer> sosuList = new ArrayList();
        for (int number : list) {
            int count = 0;
            for (int i = 1; i <= number; i++) {
                if (number % i == 0) {
                    count++;
                }
            }
            if (count == 2) {
                sosuList.add(number);
            }
        }

        // 3. 오일러 피함수 사용하기
        double num = 1;
        for (double number : sosuList) {
           num *= 1 - (1 / number);
        }
        System.out.println((int) (num * n) + "개");
    }
}

4. 소인수분해를 사용해 오일러 피함수 적용

package algo;

import java.util.ArrayList;
import java.util.List;

public class Coprime06 {
    public static void main(String[] args) {

        // 12를 소인수 분해
        int round = 0;
        int n = 12;
        int NUMBER = n;
        int 나누는수 = 2;
        int 승수 = 0;
        List<Integer> 나누는수list = new ArrayList<>();
        List<Integer> 승수list = new ArrayList<>();
        System.out.println("n = " + n);

        while (true) {
            round++;
            if (n % 나누는수 == 0) {
                n = n / 나누는수;
                승수++;
            } else {
                if (승수 != 0) {
                    승수list.add(승수);
                    나누는수list.add(나누는수);
                    나누는수 = 나누는수 + (n % 나누는수);
                    승수 = 0;
                } else {
                    나누는수 = 나누는수 + (n % 나누는수);
                }
                if (n == 1) break;
            }
        }
        System.out.println("소인수들 = " + 나누는수list);

        // 소인수를 사용한 오일러 피함수 적용
        double num = 1;
        for (double number : 나누는수list) {
            num *= 1 - (1 / number);
        }
        System.out.println("서로소의 개수 = " + (int) (NUMBER * num) + "개");
        System.out.println("반복횟수 = " + round);
    }
}