[알고리즘] 정수론

---

소수 구하기 (에라토스테네스의 체)

백준 1929번

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); // 시작 수
        int end = Integer.parseInt(st.nextToken()); // 종료 수
        int[] array = new int[end+1];
        for (int i = 2; i <= end; i++) {
            array[i] = i; // 각각의 인덱스 값으로 배열 초기화하기
        }
        for (int i = 2; i <= Math.sqrt(end); i++) { // end의 제곱근까지만 수행하기
            if (array[i] == 0) {
                continue; // 소수가 아니면 넘어감
            }
            for (int j = i + i; j <= end ; j = j + i) { // 배수 지우기 (i의 배수만큼 이동해야하기 때문에 j = j + i)
                array[j] = 0; // 이 수가 소수가 아니라는 것을 표시
            }
        }
        for (int i = start; i <= end; i++) {
            if (array[i] != 0) {
                System.out.println(array[i]); // 배열에서 소수인 값 출력하기
            }
        }
    }
}

 

- 에라토스테네스의 체에서 가장 중요한 포인트는 end 의 제곱근까지만 수행하고, 배수를 지우는 것이다.

- N의 제곱근까지만 탐색하는 이유 :

N이 a * b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없기 때문이다.

---

오일러 피 (이해도 낮음 복습할 때 다시 해보기)

백준 11689번

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine()); // 소인수 표현 입력
        long result = n; // 결괏값
        for (long p = 2; p <= Math.sqrt(n); p++) { // n의 제곱근까지만 진행하기
            if (n % p == 0) { // 만약 현재 값이 소인수라면
                result = result - result / p; // 결괏값 = 결괏값 - 결괏값/현재값
                while (n % p == 0) { // n에서 현재 소인수 내역을 제거하기
                    n /= p;
                }
            }
        }
        if (n > 1) { // n이 마지막 남은 소인수 구성일 때
            // 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스
            result = result - result / n;
        }
        System.out.println(result);
    }
}

- 오일러 피 문제는 아직 완벽하게 이해하진 못했다. 여러 번 다시 봐야할 것 같다.

- 입력에서 자연수가 10의 12제곱까지 주어지기 때문에 int 대신 long을 사용했다. 

- while (n % p == 0) 에서 2의 7제곱 * 11 이라면 2의 7제곱을 없애고 11만 남긴다. -> n에서 현재 소인수 내역 제거

---

유클리드 호제법

백준 1934번

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수가 주어짐
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int result = A * B / gcd(A, B);
            System.out.println(result);
        }
    }
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // 만약 b가 0이면, a는 최대공약수
        } else {
            return gcd(b, a % b); // 작은 수, 큰 수 % 작은 수 를 재귀 함수 형태로 구현하기
        }
    }
}

- 두 수의 최대공배수를 구하려면, 두 수의 곱을 최대 공약수로 나눈 값을 구해야함.

- 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택! 그 후에 최대 공배수를 구해주기.