[ 백준 1978 ] 소수 찾기 - 에라토스테네스의 체, 비트마스크

 

1. 문제: https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

2. 풀이

 

소수를 판별하는 방법에는 다양한 방법들이 존재하고, 이를 최적으로 판별하기 위한 방법에도 여러가지가 있다. 기본적으로 소수를 판별하기 위해서는 소수의 조건에 위배되지 않는지 일일이 확인해 보는 가장 원시적인 방법이 있겠다.

//원시시대 방법
boolean isPrime = true;
for(int i = 2; i < a; i++) {
  if(a % i == 0) {
    isPrime = false;
    break;
  }
}
String ret = isPrime? "소수" : "소수아님";

 

이 원시적인 방법에서 그나마 돌을 갈고 불을 피우면서 머리를 굴리게 된것은 반복문의 범위를 판별하고자 하는 수 a의 제곱근으로 제한하는 것이다.

boolean isPrime = true;
int sqrt_a = (int)Math.sqrt(a);
for(int i = 2; i <= sqrt_a; i++) {
  if(a % i == 0) {
    isPrime = false;
    break;
  }
}
String ret = isPrime? "소수" : "소수아님";

 

하지만 현재 문제에서는 1000이하인 N개의 자연수들 중 소수가 몇 개인지를 판별하라고 한다.

 

이러한 경우에는 매번 소수를 판별할 것이 아닌 주어진 범위(1000이하)의 자연수에 대해 소수인지의 여부를 판별해두고 입력받은 자연수들 중 몇 개가 소수인지를 판별하는 편이 훨 효율적이다.

 

이 때 필요한 것이 바로 '에라토스테네스의 체'다.

 

이미 이것은 너무나도 많이 알려져 있고 크게 어려운 내용도 없는 관계로 설명은 위키에 넘기고 이를 구현해보도록 한다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class FindPrime1978 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //에라토스테네스의 체 기본 ver.
		Eratos_1 eratos = new Eratos_1();
        //에라토스테네스의 체 비트마스크 ver.
		Eratos_2 eratos_2 = new Eratos_2();
        //입력
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		int cnt = 0;
		int cnt_2 = 0;
		for(int i = 0; i<N; i++) {
			int n = Integer.parseInt(st.nextToken());
			if(eratos.isPrime(n))
				cnt++;
			if(eratos_2.isPrime(n))
				cnt_2++;
		}
		
		bw.write(String.format("%d, %d", cnt, cnt_2));
		bw.flush();
		bw.close();
		br.close();
	}
	
    //에라토스테네스의 체 기본형
	static class Eratos_1 {
		private final int MAX = 1000;
		private boolean sieve[];
		
		public Eratos_1() {
			sieve = new boolean[MAX + 1];
			Arrays.fill(sieve, true);
			
			int sqrt_max = (int)Math.sqrt(MAX);
			sieve[0] = sieve[1] = false;
			for(int i = 2; i <= sqrt_max; i++) {
				if(sieve[i]) {
					for(int j = i*i; j <= MAX; j += i)
						sieve[j] = false;
				}
			}
		}
		
		public boolean isPrime(int num) {
			return sieve[num];
		}
	}
	
    //에라토스테네스의 체 비트마스크형
	static class Eratos_2 {
		private final int MAX = 1000;
		private int sieve[];
		
		public Eratos_2() {
			sieve = new int[(MAX / 8) + 1];
			Arrays.fill(sieve, 255); 
			setComposite(0);
			setComposite(1);
			
			int sqrt_max = (int)Math.sqrt(MAX);
			for(int i = 2; i <= sqrt_max; i++) {
				if(isPrime(i)) {
					for(int j = i*i; j <= MAX; j += i)
						setComposite(j);
				}
			}
		}
		
		public boolean isPrime(int n) {
			return (sieve[n >> 3] & (1 << (n & 7))) != 0;
		}
		
		private void setComposite(int n) {
			sieve[n >> 3] &= ~(1 << (n & 7));
		}
	}
}

 

Eratos_1 클래스 부분을 먼저 살펴본다.

boolean 배열을 선언해 소수의 배수들을 지워나가는 과정으로 유의깊게 봐야할 부분은 아래와 같다.

for(int j = i*i; j <= sqrt_max; j += i)

j가 max까지가 아닌 max의 제곱근까지만 탐색하는 것은 제곱근 이상의 경우 기본적으로 소수판별식의 메커니즘과 동일하다. 다만 구구단처럼 i*2부터 시작하는 것이 아닌 i*i부터 시작하는 이유는 이미 이전에 i가 2, 3일 경우에 지워졌을 것이기 때문이다. 로직자체에 큰 어려움은 없다.

 

Eratos_2 클래스 부분을 보자.

체는 일일이 소수판별식을 돌리는 것에 비해 월등한 속도를 자랑하지만 체를 적용시켜야할 범위가 기하급수적으로 늘어났을 경우에 대해 생각해봐야 한다.

 

32비트 정수가 표현 하는 모든 수에 대해 체를 수행하게 된다고 했을 때, 기존 체와 같이 boolean 배열을 사용하게 되면 4GB까지 메모리를 와구와구 먹는다. 하지만 비트마스크를 사용하게 된다면 이 메모리의 사용을 압도적으로 줄일 수 있다.

 

https://kwanik.tistory.com/3?category=862597

비트마스크[BitMask]란?

체를 적용시키고자 하는 범위의 수를, 8bit 단위(8개로) 잘라서 각각의 수에 대해 체를 적용시킨다면 (MAX/8 + 1)개의 int 배열만으로 대체될 수 있다. 물론 8bit가 아닌 16bit, 4bit와 같이 다른 2진수 단위로 잘라넣어도 무방하다.

 

(사실 본 문제는 예전에 풀었으나 킹종만북을 보면서 무릎을 탁 치고 이를 적용시켜 푼 것이다.)

 

체를 풀이하는 핵심 로직은 동일하다.

다만 체를 적용하고, 소수인지를 확인하기 위해 비트마스크를 사용하는 것인데 주요한 로직은 아래와 같다.

//에라토스테네스의 체 비트마스크형
static class Eratos_2 {
	private final int MAX = 1000;
	private int sieve[];

	public Eratos_2() {
		sieve = new int[(MAX / 8) + 1];
		Arrays.fill(sieve, 255); 
		setComposite(0);
		setComposite(1);

		int sqrt_max = (int)Math.sqrt(MAX);
		for(int i = 2; i <= sqrt_max; i++) {
			if(isPrime(i)) {
				for(int j = i*i; j <= MAX; j += i)
					setComposite(j);
            }
		}
	}

	public boolean isPrime(int n) {
		return (sieve[n >> 3] & (1 << (n & 7))) != 0;
	}

	private void setComposite(int n) {
		sieve[n >> 3] &= ~(1 << (n & 7));
	}
}

 

1. 오른쪽 쉬프트(shift, >>)

오른쪽 쉬프트는 2^N으로 나누는 것을 의미한다. 즉 소수가 아닌 수를 지우고, 판별하기 위해 해당 수가 배열의 몇 번째 칸에 들어있는지 확인하기 위한 부분이다.

 

2. 나머지 연산(n & 7)

해당 숫자가 몇 번째 배열에 위치해있는지 알았다면(8로 나눈 몫), 배열 안에서 다시 몇 번째(8로 나눈 나머지)에 위치한지를 알아야 한다. 이를 위해 n & 7 연산을 수행하고 이만큼 1을 왼쪽 쉬프트를 진행한다.

 

배열의 첫 번째 칸인 0 ~ 7 범위를 예로 들어본다.( 1111 1111 로 초기화 되있는 상태)

1. setComposite(0)
1111 1111 & ~(1 << (0 & 7))
-> 1111 1111 & ~0000 0001
-> 1111 1111 & 1111 1110
-> 1111 1110

2. setComposite(1)
1111 1110 & ~(1 << (1 & 7))
-> 1111 1110 & ~0000 0010
-> 1111 1110 & 1111 1101
-> 1111 1100

...
-> 1010 1100

1. isPrime(3)
1010 1100 & (1 << (3 & 7))
-> 1010 1100 & 0000 1000
-> 0000 1000 (Prime!)

2. isPrime(4)
1010 1100 & (1 << (4 & 7)
-> 1010 1100 & 0001 0000
-> 0000 0000 (Not Prime!)

 

아직 비트마스크가 그리 직관적으로 다가오지 않아 직접 디버깅하면서 적어보는 것이 가장 쉽게 이해가 된다. 문제 풀이에 적용을 하기에는 분명 어려운 부분이 있으나 메모리를 혁식적으로 줄여주는 것은 익혀둘만한 가치가 있는 것 같다.

 

---

 

Reference

1. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2권_비트마스크_575p_구종만 지음