BOJ 4913 페르마의 크리스마스 정리

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

4913번: 페르마의 크리스마스 정리

 

풀이 자체는 어렵지 않은 문제입니다. 음수는 소수가 아니므로, 1부터 1000000 사이의 모든 소수를 에라체를 이용해 미리 구해준 뒤 누적합을 이용해 매 쿼리마다 소수의 개수와 제곱수의 합으로 표현되는 소수의 개수를 구해주면 됩니다.

 

단, 주의해야 할 점은 2 역시 제곱수의 합으로 표현되는 소수라는 점입니다. (1 + 1 = 2)

 

이걸 몰라서 세 번 틀렸습니다...

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, sieve[1000010], prime[1000010], square[1000010];

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;
  
  square[2] = 1;

  for (int i = 2; i <= 1000000; i++) {
    if (sieve[i]) continue;
    prime[i]++;
    if ((i - 1) % 4 == 0) square[i]++;
    for (int j = i + i; j <= 1000000; j += i) sieve[j]++;
  }

  for (int i = 1; i <= 1000000; i++) {
    prime[i] += prime[i - 1];
    square[i] += square[i - 1];
  }

  while (1) {
    int l, r;
    cin >> l >> r;

    if (l == -1 && r == -1) break;

    if (r < 1) {
      cout << l << ends << r << ends << 0 << ends << 0 << endl;
      continue;
    }

    cout << l << ends << r << ends;
    cout << prime[r] - prime[max(0, l - 1)] << ends;
    cout << square[r] - square[max(0, l - 1)] << endl;
  }

  return 0;
}