백준(BOJ) 2581 소수

에라토스테네스의 체를 이용하여 풀었다.

비트연산도 연습할겸, 비트연산을 넣어보았다.

비트연산에 익숙해지는 것이 생각보다 어려운 것 같다.

기회되는대로 다양한 구현을 해봐야겠다.

사용한 비트연산 기법으로는 

나누기 대신 >> 연산자를 이용하였고

% 연산 대신 & 7을 사용하였다.

전체 배열의 비트를 1로 세팅하였고,

char 배열에 넣었으므로, 1/8 압축했다.

비트는 1로 채워져있고 0으로 세팅해야하기에

a &= ~(1 << (k & 7)) 을 활용하여 0으로 클리어하였다.

비트가 세트되어있는지 확인은 & 를 활용하였다.

소수를 체킹하면서 소수를 배열이나 벡터에 따로 저장 할 수도 있다.

그렇게 하려면 i를 루트n이 아니라, n까지 돌면 된다. 

하지만 이렇게 할 경우 j = i * i 연산에서 오버플로우가 발생할 가능성이 있다. 

때문에  j = i + i 로 시작하여 오버플로우를 방지하자!

#include <cstdio>
unsigned char isPrime[1251];
 
bool isPr(int k){
    if(isPrime[k >> 3] & (1 << (k & 7))){
      return true;
    }
 
    return false;
}
 
void setComposite(int k){
    isPrime[k >> 3] &= ~(1 <<(k & 7));
}
int main() {
    for(int i = 0; i < 1251; i++){
        isPrime[i] = 255;
    }
    int m, n;
    scanf("%d %d", &m , &n);
 
    setComposite(1);
    setComposite(0);
    for(int i = 2; i*i <= n; i++){
        if(isPr(i)){
            for(int j = i * i; j <= n; j += i){
                setComposite(j);
            }
        }
    }
    int mi = 0;
    int sum = 0;
    for(int i = m; i <= n; i++){
        if(isPr(i)){
            if(mi == 0){
                mi = i;
            }
            sum+= i;
        }
    }
    if(sum == 0) printf("-1\n");
    else  printf("%d\n%d", sum, mi);
 
 
    return 0;
}