[BOJ] 수학 2(1)

오늘은 수학 2단계의 전반부를 풀어보겠습니다. 소수에 관한 문제들입니다. 이번 시간에 소수에 관한 문제를 풀 때는 알고리즘을 2개만 알면 됩니다.

 

먼저 하나의 소수가 주어졌을 때 해당 수가 소수인지 아닌지 판단하는 경우입니다.

bool isprime(int n){
    if(n==1) return false;
    for(int k=2;k*k<=n;++k)
        if(n % k == 0)
            return false;
    return true;
}

일일이 나머지가 0인 게 있는지 확인해보는 것입니다. 실제 검사를 할 때는 제곱이 n보다 작거나 같은 경우까지만 검사하면 됩니다. 그 이후에 약수가 있는 경우 그 이전에도 반드시 약수가 있기 때문입니다.

 

그다음으로는 에라토스테네스의 체라는 것입니다. 

class primesift{
    public:
        vector<bool> isprime;
        primesift(int lim) : isprime(lim + 1, true){
            isprime[0] = false;
            isprime[1] = false;
            for(int p=2;p*p<=lim;++p){
                for(int k=2*p;k<=lim;k+=p)
                    isprime[k] = false;
            }
        }
};

위와 같이 2중 for문으로 구해주었습니다. 바깥 for문은 첫 번째 알고리즘에서 하듯이 여러 숫자를 돌면서 검사를 해주는 겁니다. 내부 for문은 해당 숫자의 배수들에 대해서 소수가 아님을 확인하고 false로 바꿔주는 겁니다. 

 

이렇게 설명했으면 더 이상 설명은 필요할 것 같지 않네요. 코드를 보고 마치겠습니다.

 

[BOJ 1978]

 

#include <iostream>

using namespace std;

bool isprime(int n){
    if(n==1) return false;
    for(int k=2;k*k<=n;++k)
        if(n % k == 0)
            return false;
    return true;
}

int main() {
    int N;
    scanf("%d",&N);
    int count = 0;
    for(int k=0;k<N;++k){
        int n;
        scanf("%d",&n);
        if(isprime(n))
            count++;
    }
    printf("%d",count);
}

 

[BOJ 2581]

 

#include <stdio.h>
#include <vector>

using namespace std;

class primesift{
    public:
        vector<bool> isprime;
        primesift(int lim) : isprime(lim + 1, true){
            isprime[0] = false;
            isprime[1] = false;
            for(int p=2;p*p<=lim;++p){
                for(int k=2*p;k<=lim;k+=p)
                    isprime[k] = false;
            }
        }
        int intervalsum(const int L, const int R){
            int primesum = 0;
            for(int k=L;k<=R;++k){
                if(isprime[k]){
                    primesum += k;
                }
            }
            return primesum;
        }
        int intervalmin(const int L, const int R){
            for(int k=L;k<=R;++k){
                if(isprime[k]){
                    return k;
                }
            }
            return -1;
        }
};

int main(){
    int M, N;
    scanf("%d%d",&M,&N);
    
    primesift P(N);
    int ressum = P.intervalsum(M, N);
    if(ressum>0)
        printf("%d\n%d\n",ressum, P.intervalmin(M, N));
    else
        printf("-1\n");
}

 

[BOJ 1929]

 

정답 풀이들을 보니까 이거보다 더 최적화를 하신 분들이 있더라고요. 요약하면 구간합 알고리즘을 약간 섞어주면 됩니다. 구간합 알고리즘은 처음부터 누적합을 구해놓은 다음에 필요한 구간의 양 끝의 누적 값의 차이로 구하는 겁니다. 이렇게 구하면 각 구간을 일일이 검사할 필요 없이 한방에 구할 수 있게 됩니다. 

#include <stdio.h>
#include <vector>

using namespace std;

class primesift{
    public:
        vector<bool> isprime;
        primesift(int lim) : isprime(lim + 1, true){
            isprime[0] = false;
            isprime[1] = false;
            for(int p=2;p*p<=lim;++p){
                for(int k=2*p;k<=lim;k+=p)
                    isprime[k] = false;
            }
        }
};

int main(){
    int M, N;
    scanf("%d%d",&M,&N);
    
    primesift P(N);
    for(int k=M;k<=N;++k){
        if(P.isprime[k]){
            printf("%d\n",k);
        }
    }
}

 

[BOJ 4948]

 

#include <stdio.h>
#include <vector>

using namespace std;

class primesift{
    public:
        vector<bool> isprime;
        primesift(int lim) : isprime(lim + 1, true){
            isprime[0] = false;
            isprime[1] = false;
            for(int p=2;p*p<=lim;++p){
                for(int k=2*p;k<=lim;k+=p)
                    isprime[k] = false;
            }
        }
        int intervalcount(const int L, const int R){
            int primecount = 0;
            for(int k=L;k<=R;++k){
                if(isprime[k]){
                    primecount++;
                }
            }
            return primecount;
        }
};

int main(){
    vector<int> inputs;
    int IN, INMAX = 0;
    while(true){
        scanf("%d",&IN);
        if(IN == 0) break;
        inputs.push_back(IN);
        if(IN > INMAX)
            INMAX = IN;
    }
    
    primesift P(INMAX*2);
    for(const int IN : inputs){
        printf("%d\n",P.intervalcount(IN+1, IN*2));
    }
}

 

[BOJ 9020]

 

#include <stdio.h>
#include <vector>

using namespace std;

class primesift{
    public:
        vector<bool> isprime;
        primesift(int lim) : isprime(lim + 1, true){
            isprime[0] = false;
            isprime[1] = false;
            for(int p=2;p*p<=lim;++p){
                for(int k=2*p;k<=lim;k+=p)
                    isprime[k] = false;
            }
        }
        int goldbach(const int P){
            for(int n=P/2;n>=2;--n){
                if(isprime[n] && isprime[P - n]){
                    return n;
                }
            }
            return -1;
        }
};

int main(){
    int T;
    scanf("%d",&T);
    
    vector<int> inputs(T);
    int IN, INMAX = 0;
    for(int k=0;k<T;++k){
        scanf("%d",&IN);
        inputs[k] = IN;
        if(INMAX < IN)
            INMAX = IN;
    }
    
    primesift P(INMAX);
    for(const int IN : inputs){
        int partition = P.goldbach(IN);
        printf("%d %d\n",partition, IN - partition);
    }
}

 

수고하셨습니다.