240327 TIL - 에라토스테네스의 체

오늘은 소수찾기에 사용되는 에라토스테네스의 체에 대해 알아 보았다. 

소수를 찾는 방법

1. N보다 작은 자연수로 나누기

public boolean isPrime(int n) {
	if(n<=1) return false;
    	
	for(int i=2; i<n; i++) {
            if(n % i == 0) return false
	}
	return true;
}

n이 주어졌을 때 1보다 크고 n보다 작은 수로 모두 나눈 후 소수인지 아닌지 판별하는 알고리즘 n까지의 과정을 모두 검사하기 때문에 시간 복잡도는 O(N)

 

  2. N의 제곱근보다 작은 자연수로 나누기

public boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {	
        if (n % i == 0) return false;
    }
    return true;
}

해당숫자의 제곱근까지 나누기 때문에 시간 복잡도는 O(√N)

 

  3. 에라토스테네스의 체

1. 2부터 N까지의 수를 나열
2. 2부터 가장 작은 수를 소수로 정하고 2의 배수를 모두 지움
3. 지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지움

public class Main {

    public static void main(String[] args) {
        solution(120);
    }

    public static void solution(int n) {
        boolean[] prime = new boolean[n + 1]; // 0~n 만큼 배열생성

        for(int i=0; i< prime.length; i++) {
            prime[i] = true; // 기본값 true로 변경
        }
        
				// 0과 1은 소수가 아님 
        prime[0] = false; 
        prime[1] = false;

        for (int i = 2; i < Math.sqrt(n); i++) { // 2부터 n의 제곱근까지
            if(prime[i]) { // i가 소수이면
		            // 소수 i 자신을 제외한 소수의 배수에 해당하는 index false로 변경
                for (int j = i * i; j <= n; j += i) { 
                    prime[j] = false;
                }
            }
        }

        for (int i = 0; i < prime.length; i++) {
            if(prime[i]) {
                System.out.println(i);
            }
        }
    }
}

 

에라토스테네스의 체의 시간 복잡도는 O(Nlog(log N))이다.

 

이렇게 세가지 방법을 알아보았는데 처음 소수 구할때는 첫번째 방식처럼 1부터 n까지 모두 구했는데 알고리즘 문제를 풀 수록 시간문제에 걸렸고 두 번째 방법대로 제곱근까지 구하는 식으로 했을때 시간이 많이 절약되었다. 그리고 세번째 방법인 에라토스테네스의 체를 사용하면 가장 효율적이라고 하니 이제부터 소수문제를 풀 때는 에라토스테네스의 체를 많이 사용해 숙련도를 높여야겠다.