(백준 알고리즘 문제풀이) 9020번 골드바흐의 추측

문제

어떻게 접근할 것인가?

인풋 중에 가장 큰 수를 찾는다.

에라토스테네스의 체를 이용해서 소수를 찾는다.

각 수의 반반부터 시작해서 두수가 모두 소수인 경우를 찾아서 출력한다.

코드

#include <cstdio>
#include <vector>

using namespace std; 

int main(){
    int n = 0, m = 0;
    int check[300000] = {0,};
    vector<int> v;
    while(1){
        scanf("%d", &n);
        if(n == 0) break;
        if(n > m) m = n;
        v.push_back(n);
    }
    for(int i = 2; i <= m*2; i++){
        if(check[i] == 0){
            for(int j = i*2; j <= m*2; j+=i)check[j] = 1;
        }
    }

    for(int  i = 0; i < v.size(); i++){
        int count = 0;
        for(int j = v[i]+1; j <= v[i]*2; j++) if(check[j] == 0){
            count++;
        }
        printf("%d\n", count);
    }

}

느낀점

끝!