3977. 페르마의 크리스마스 정리

3977. 페르마의 크리스마스 정리

처음 문제를 보고는 그냥 에라토스테네스의 체를 이용해서 문제를 푸는구나 했다.

에라토스테네스의 체를 미리 한번만 구하도록 했는데, 시간초과가 발생했다. 

그래서 아! DP문제로 다시 풀 수 있겠구나하고 제출했는데.. 정답이 계속 틀렸다.. 분명 코드는 맞는거 같은데

그러다가 문제의 댓글에 나와 똑같은 분을 봤는데..

예외적으로 2라는 값은 4로 나누었을 때 1이 아니지만, 1^2 + 1^2 이므로 정답에 해당했다..!

아주 큰 예외를 생각하지 못하고 있었다.

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
const int MAX = 1000001;
bool prime[MAX];
int D[MAX];
void era()
{
    for (int i = 2; i*i < MAX; i++)
    {
        if (prime[i])
        {
 
            for (int j = i+i; j < MAX; j += i)
            {
                prime[j] = false;
            }
        }
 
    }
 
    int sum = 0;
    for (int i = 1; i < MAX; i++)
    {
        if (prime[i] && i % 4 == 1)
        {
            sum++;
        }
        D[i] += sum;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    era();
 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int s, e, ans;
        cin >> s >> e;
        ans = D[e] - D[s - 1];
    
        if (s <= 2)
        {
            ans += 1;
        }
 
        cout << "#" << t << " " << ans << "\n";
 
    }
 
    return 0;
}