알고리즘 공부를 시작한 학생인데요
오늘 비트마스크에 대해 공부했는데 소수를 구하는 알고리즘을 짜고 있었어요
그런데 이놈이 4시간동안 인터넷 찾고 고치고 반복을 해도 안되더니
질문할 생각으로 코드를 좀 보기 이쁘게 고쳤는데
정상적으로 실행이 되네요...??? ㅎㅎ.....
그래서 기분이 무지 좋습니다. 하하하
그나저나 시중에 C 또는 C++관련 책만 나와있어서 굉장히 속상하네요
자바 개발자들을 위해서 자바로 된 책들이 많이 나왔으면 좋겠습니다.
이게 그 문제의 에라토스테네스의 체를 비트마스크로 구현한 소스코드 입니다.
(소스가 지저분하고 허접한건 빨리 풀고싶은 급한마음에... ㅎㅎ)
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){
if((sieve[k>>3] & (1<<(k&7))) >0)
return true;
else
return false;
}
void setComposition(int k){
sieve[k>>3] &= ~(1<<(k&7));
}
void eratos(){
for(int i=0;i<sieve.length;i++)
sieve[i]=65535;
setComposition(0);
setComposition(1);
int numSize=n;
for(int i=2;i<=numSize;i++)
if(isPrime(i))
for(int j=i*i; j<=n; j+=i)
setComposition(j);
}
/*public void printEratos(){
for(int i=0;i<sieve.length;i++)
System.out.print((int)sieve[i]+" ");
}*/
public static void main(String[] args){
Eratos sample=new Eratos(100);
sample.eratos();
//sample.printEratos();
for(int i=0; i<100; i++){
System.out.print(i+"="+sample.isPrime(i)+" ");
if(i%10==0)
System.out.println();
}
}
}
글쓰기