[코딩테스트] 호제법, 소인수분해, 에라토스테네스의 체(소수 구하기) - 정수론

(유클리드) 호제법(Euclidean Algorithm)

• 두 정수의 최대공약수(gcd; Greatest Common Divisor)를 쉽게 알아내는 방법
• gcd(0, A) = A
• 모든 수는 0을 나눌 수 있다. 따라서, 0의 모든 약수는 임의의 정수 A를 포함한다. 
• 따라서, 둘의 gcd는 A가 된다. 
• gcd(a,b) = gcd(b, a%b) (단, a > b) -- b > a이면 값을 바꾼다

 

 

cf. 귀류법

• 어떤 명제가 참임을 직접 증명하는 대신, 그 부정 명제가 참이라고 가정하여 그것의 불합리성을 증명함으로써 원래의 명제가 참인 것을 보여 주는 간접 증명법. [네이버사전]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }
        int gcd = gcd(a, b);
        System.out.println(gcd); // 최대공약수
        System.out.println(a * (b / gcd)); // 최소공배수
    }

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

 

반복문으로 gcd 구해서 최소공배수 구하기

private static int lcm(int a, int b) {
    int tmp1 = a, tmp2 = b;
    if (b > a) {
        a = tmp2;
        b = tmp1;
    }
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return tmp1 * (tmp2 / a);
}

 

에라토스테네스의 체

• 대량의 소수를 한꺼번에 판별하고자 할 때 사용
• 마치 체를 치듯이 수를 걸러낸다고 하여 에라토스테네스의 '체'라고 부른다
• 소수의 배수를 제외함으로써(지움으로써) 소수만 걸러낸다
• cf. 일반적인 반복문으로 주어진 숫자의 제곱근까지만 약수의 여부를 검증해도 된다 => O(N^(1/2))

public class Sieve {
    public static void main(String[] args) {
        sievePrime();
    }

    private static void sievePrime() {
    	int num = 100;
        int[] ns = new int[101];
        for (int i = 2; i <= num; i++) {
            ns[i] = i;
        }
        for (int i = 2; i <= (int)Math.sqrt(num); i++) {
            if (ns[i] == 0) continue;
            for (int j = i + i; j <= num; j+=i) {
                ns[j] = 0;
            }
        }
        for (int i = 2; i <= num; i++) {
            if(ns[i] != 0) System.out.print(ns[i]+" ");
        }
    }
}

https://www.youtube.com/watch?v=T5aD-mcQtKo

 

 

https://www.youtube.com/watch?v=J5Yl2kHPAY4

 

 

유클리드 호제법 (개념 이해하기) | 모듈로 연산 | Khan Academy

 

[Algorithm] 에라토스테네스의 체

https://blog.naver.com/ndb796/221233595886

22. 에라토스테네스의 체