[백준 / BOJ] C++ 14941

#14941: 호기심

문제

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

설명

규칙에 따라 a보다 크고 b보다 작은 소수를 계산하는 것은 간단한 문제입니다. 먼저 에라토스테네스의 체를 사용하여 10^5보다 작은 소수를 걸러냅니다. 소수가 하나보다 큰지 여부를 비교하는 방법은 O(N)의 시간 복잡도를 가지며, 10^5보다 작은 소수가 41,000개 이상 있고 테스트 케이스의 수 N이 10^5이므로 시간이 초과됩니다. 따라서 프라임 배열이 이미 정렬되어 있으므로 O(logN)의 시간 복잡도를 갖는 이진 검색을 사용했습니다.

C++ STL 하한그리고 상한 함수를 사용하여 a보다 큰 요소가 먼저 발견되는 반복자를 찾고 b보다 큰 요소가 먼저 나타나는 반복자를 각각 s와 e로 찾습니다. s에서 e까지의 각 값은 for 문으로 참조되었습니다. 이제 홀수 연산의 경우 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;
}