[백준 / BOJ] C++ 14941 호기심

14941번: 호기심

 

문제

https://www.acmicpc.net/problem/14941

14941번: 호기심

 

 

풀이

a 이상 b 이하의 소수를 규칙에 따라 계산하는 간단한 문제다. 먼저 에라토스테네스의 체를 사용해 10^5보다 작은 소수를 걸러낸다. 소수를 하나하나 a보다 큰지 비교하다는 방법은 시간복잡도가 O(N)이고 10^5 이하의 소수는 약 41,000개 이상이고 테스트케이스의 수 N이 10^5이기 때문에 시간초과가 난다. 따라서 prime 배열은 이미 정렬이 되어있기에 시간복잡도가 O(logN)인 이분 탐색을 사용해 줬다.

 

C++ STL인 lower_bound와 upper_bound 함수를 사용해 a 이상인 원소가 처음 등장하는 iterator와 b 이상인 원소가 처음 등장하는 iterator를 각각 s와 e로 찾아준다. for문으로 s부터 e 전까지 각 값을 참조했다. 이제 홀수번째 연산에서는 3을 곱해서 더해주고, 짝수번째 연산에서는 -1을 곱해서 더하도록 했다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> sieve(500001, 1), prime;
  for (int i = 2; i <= 500000; i++)
    if (sieve[i]) {
      prime.push_back(i);
      for (int j = i * 2; j <= 500000; j += i)
        sieve[j] = 0;
    }
  while (n--) {
    int a, b, cnt = 1, ans = 0;
    cin >> a >> b;
    auto s = lower_bound(prime.begin(), prime.end(), a);
    auto e = upper_bound(prime.begin(), prime.end(), b);
    for (auto it = s; it != e; it++, cnt++)
      if (cnt % 2)
        ans += 3 * *it;
      else
        ans -= *it;
    cout << ans << '\n';
  }
  return 0;
}