[Algorithm] JAVA 소수판별 - 에라토스테네스의 체

 

 

ㅇ 소수란?

 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

 

예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다.

 

 

ㅇ 소수 찾기

소수를 찾는 방법은 총 3가지가 있다.

 

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

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

3. 에라토스테네스의 체 이용하기

 

 

 

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

첫번째 방법은 매우 간단하면서 기초적인 방법이다.

 

N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다.

 

예를 들어보자.

만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자.

 

6 / 2 = 3

6 / 3 = 2

6 / 4 = 1 ... 2

6 / 5 = 1 ... 1

 

6은 2와 3으로 나누어 떨어지기 때문에 약수가 아니다.

 

 

[N보다 작은 자연수로 나누기]

public boolean isPrime(int n) {
    if (n <= 1) return false;			// 1보다 작으면 false 반환
    for (int i = 2; i < n; i++) {		// 2보다 크고 n보다 작은 수로 나눈다.
        if (n % i == 0) return false;		// 만약 나누어 떨어지는 것이 있다면 false 반환
    }
    return true;				// 모두 나누고도 떨어지는 수가 없다면 true 반환
}

n이 주어졌을 때 1보다 크고 n보다 작은 수로 모두 나눈 후 소수인지 아닌지 판별하는 알고리즘이다.

 

N까지의 과정을 모두 검사하기 때문에 시간 복잡도는 O(N)이다.

 

 

 

 

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

이 방법은 첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 굳이 N이하까지 모두 나누어 볼 필요가 없다는 방법이다. 즉, N의 제곱근(√) 까지만 나눈다는 뜻이다.

 

다시 6으로 예를 들어보자.

 

6 / 2 = 3

6 / 3 = 2

6 / 4 = 1 ... 2

6 / 5 = 1 ... 1

 

 

√4=2   <  √6=2.xxx  < √9 = 3

 

6을 나눌 때 2까지만 나누고 3이상은 나눠보지 않아도 3은 2로 나누어 떨어진다.

때문에 √N까지만 나누어도 된다는 뜻이다.

 

 

 

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

public boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {			// n의 제곱근까지 나누기
        if (n % i == 0) return false;
    }
    return true;
}

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

 

 

 

 

 

ㅇ 에라토스테네스의 체 이용하기

다음 방법은 소수판별에서 가장 효율적인 알고리즘이다.

 

1. 2부터 N까지의 수를 나열한다.

2. 2부터 가장 작은 수를 소수로 정하고 2의 배수를 모두 지운다.

3. 지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지운다.

 

이렇게 하나씩 지워나가다 보면 지워지지 않는 수들이 있는데 이들이 바로 소수이다.

 

위키백과에 해당 애니메이션이 있는데 이해하기 쉬워보여 가지고 왔다.

출처 : 위키백과(에라토스테네스의 체)

먼저 가장 작은 수인 2를 소수로 등록한 후, 2의 배수를 지운다. 

지우지 않은 수 중 가장 작은 수인 3을 소수로 등록한 후, 3의 배수를 지운다.

이를 계속 반복하는 것이다.

 

 

 

[에라토스테네스의 체]

public boolean[] sieveOfEratosthenes(int n) {

    //0부터 n까지의 수이기 때문에 n+1을 할당한다.
    boolean[] prime = new boolean[n+1];
    
    // 0과 1은 소수가 아니기 때문에 false를 저장한다.
    prime[0] = false;				
    prime[1] = false;
    
    // n의 제곱근까지 나눈다.
    for(int i = 2; i <= Math.sqrt(n); i++) {
        
        	// 소수라면 뒤에 오는 코드를 스킵한다.
		if(prime[i] == true) {
			continue;
		}
        
		// 2부터 배수에 해당하는 수를 true로 변환한다.
		for(int j = i * i; j < prime.length; j = j+i) {
			prime[j] = true;
        	}
	}
    return prime;
}

 

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

 

N이하의 소수를 판별하는 것만 따지면 O(NlongN)이다.

 

하지만 여기서 이미 배수로 체크된 수는 나누지 않고 넘어간다. 즉, 최종적으로 정리하면 총 시간복잡도는 O(Nlog(log N))임을 알 수 있다.