에라토스테네스의 체 & 유클리드 호제법

에라토스테네스의 체 시간 복잡도

에라토스테네스의 체는 소수를 찾는 방법이다. 대량 소수를 찾는데 최적화된 방법이다. 원래 두 수 사이의 소수를 구하려면 시간 복잡도가 아마 O(N^2)가 걸릴 텐데, 에라토스테네스의 체를 이용하면 O(Nlog(logN))이 된다. 그래서 많은 소수를 구하려면 이 방법을 사용해야 TLE가 걸리지 않는다.

 

에라토스테네스의 체 개념

소수의 배수들을 체크하여 체크하지 않은 곳이 바로 소수이다. 구하려는 소수의 범위에서 2, 3, 5, 7 ... √n까지의 배수들을 체크하고, 체크하지 않은 곳들을 출력하면 소수들을 구할 수 있다.

 

에라토스테네스의 체 구현코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        for(int i = 2; i <= num2; i++){
            if(visit[i] == false) continue;
            
            for(int j = 2 * i; j <= num2; j += i)
                visit[j] = false;
        }
}

일단 처음에 visit배열을 boolean형으로 선언하고, Arrays.fill()을 이용하여 visit를 true로 초기화시켰다. 그리고 처음 포문은 i가 2부터 시작한다.(1은 소수가 아니기 때문) 그래서 방문을 한 곳은 continue로 넘어가고, 그다음 포문에서 2의 배수들을 방문한다. 그래서 j += i는 2의 배수를 차근차근 방문한다는 것이고, num2는 구하려는 소수의 최대 범위를 나타낸다. 

 

유클리드 호제법 시간 복잡도

두 수의 최대 공약수를 구할 때 처음부터 나눠서 공통 인수를 구하여, 그중에서 가장 큰 값을 고르는 시간 복잡도는 O(N)이다. 그러나 만약 유클리드 호제법을 이용하여 최대 공약수를 구하면 O(log(n+m))에 구할 수 있게 된다. 

 

유클리드 호제법 개념 

GCD : 최대공약수    LCM : 최소공배수

a > b일 때,

GCD(a, b) = GCD(b, a % b)이다. 여기서 두 번째 인자가 0이 될 때까지 시행하고, 그때의 첫 번째 인자가 최대공약수이다. 

ex) GCD(28,12) = GCD(12, 4) = GCD(4, 0) 따라서 최대 공약수는 4가 된다.

그래서 LCM = a * b / GCD이다.

 

유클리드 호제법 구현 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        while(min != 0){
            int temp = max % min;
            max = min;
            min = temp;
        }
}

여기서 min이 0이 될 때의 max의 값이 GCD가 된다. 

GCD(max, min) = GCD(min, temp)라고 생각하면 된다.