모르겠음..[JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현

[JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현

[JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현
<'알고리즘 문제 해결 전략'의 내용 다수 포함>

에라토스테네스의 체 란


















<이미지 출처 : http://study.zum.com/book/14467>


 위 그림과 같이 자연수 n이하의 소수를 구하는 알고리즘 으로써, 소수가 아닌 수의 배수를 전부 지워나가는 방법이다.
 자세히 설명해 보자면
1) 2는 소수이므로 2의 배수를 전부 지운다.
2) 다음으로 3또한 소수이므로 3의 배수를 전부 지운다.
3) 4는 이미 1번에 의해 지워졌으므로 5로 넘어간다.
4) 5는 남아있으므로 소수가 아니다. 그러므로 5의 배수를 지운다.
5) 이런방법으로 n이하의 자연수 중에 남아있는 수를 탐색한 다음에 그 수의 배수를 전부       지운다.

 굉장히 쉬운 원리이고 굉장히 빠르게 동작하지만, n이 커지면 커질수록 메모리 사용량의 문제가 생긴다. 메모리 사용량을 줄이기 위한 방법중 하나로 비트마스크를 활용하는 것이다. boolean값을 갖는 배열을 사용한다면 N바이트의 배열을 사용해야 하지만 비트마스크를 이용하여 char배열을 생성한다면 N/8바이트 만 사용하여 만들 수 있다.

 아래의 소스코드를 설명해 보자면, 2진수에서 0은 소수가 아닌 수를 의미하고, 1은 소수인 수를 의미한다. 즉 소수가 아닌수를 발견하면 0으로 바꾸고 소수인 수는 그대로 냅둔다.
(2진수의 초기값은 1111 1111 으로 설정한다.)
 배열 sieve는 한 배열당 2바이트를 차지하지만 여기선 1바이트(8비트)만 사용하였다. 즉 한 배열당 8개의 숫자 정보를 저장할 수 있다. (1111 1111 이므로 총 8개의 숫자정보를 입력 할 수 있다.)
 이렇게 되면 그냥 boolean배열을 선언하는 것 보다 훨씬 많이 메모리를 절약할 수 있다. 그리고 자바에선 char가 유일한 unsigned(양수만 표현하는) 자료형 이므로 비트관련 연산에선 char자료형을 사용하는 것이 좋다.

package bitMask;

public class Eratos {
public int n;
public final static int MAX_N=100;
public char[] sieve=new char[(MAX_N+7)/8];

Eratos(int n){
this.n=n;
}
public boolean isPrime(int k){
               //k>>3은 k를 8로 나눈것 과 같다.(비트 이동 연산자 사용)
               //k&7은 k를 8로 나눈 나머지와 같고, 1을 8로 나눈 나머지 만                //큼 왼쪽으로 이동한 위치가 찾고자 하는 k의 위치이다.
if((sieve[k>>3] & (1<<(k&7))) >0)
return true;
else
return false;
}
// 소수가 아닌 합성수 일 경우 ~연산과 &연산을 통해 0으로 바꾼다.
void setComposition(int k){
sieve[k>>3] &= ~(1<<(k&7));
}
void eratos(){
for(int i=0;i<sieve.length;i++)
sieve[i]=255;
setComposition(0);
setComposition(1);
int numSize=n;
//여기서 i<n의 제곱근 만큼만 반복해도 된다.
         //합성수 p*q에서 p나 q중 하나는 n의 제곱근보다 작을 수 밖에 없다.
         //2부터 시작하여 배열에 남아있는 수의 배수를 전부 지운다.
         //이런 원리로 시작하면 2는 별다른 설정 없이 소수로 간주한다.
for(int i=2;i<=numSize;i++)
if(isPrime(i))
for(int j=i*i; j<=n; j+=i)
setComposition(j);

}

public static void main(String[] args){
Eratos sample=new Eratos(100);
sample.eratos();
for(int i=0; i<100; i++){
System.out.print(i+"="+sample.isPrime(i)+" ");
if(i%10==0)
System.out.println();

}
}
}

'알고리즘 문제 해결 전략'은 C++로 되어있어서 Java로 바꾸는데 좀 힘들었다...(실력이 딸려서 더욱 더욱 힘들었다...) 막상 고생끝에 바꾸고 보니까 거의 똑같아서 허무했지만ㅎㅎ
Java로 공부하는 분에게 도움이 되었으면 좋겠다.

http://minhard.blogspot.kr/2015/01/java.html