문제

문제 링크

어떻게 접근할 것인가?

  • 일단 가장 큰 수를 찾는다.
  • 에라토스테네스의 체를 이용해서 소수를 찾는다.
  • 각 수의 범위에 있는 소수를 찾아 출력한다.

코드

#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);
    }
}

느낀점

  • 잘짠 코드에 보니 algorithm을 통해서 upper과 lower bound를 이용했던데 그것도 공부해봐야겠다.