3977. 페르마의 크리스마스 정리(D5)

문제에서 소수 p를 4로 나눈 나머지가 1이면 p= a^2+b^2 을 만족한다고 나와있다.

그러므로 먼저 소수를 계산한 다음, 주어진 범위 내에서 4로 나눈 나머지가 1인 소수를 찾는다.

#include <stdio.h>
#include <math.h>
int arr[500000] = { 2,3,5,7, };
int cnt = 4;
int main(void) {
    for (int i = 11; i<1000000; i++) {
        int check = 0;
        for (int j = 0; j < cnt; j++) {
            if (i%arr[j] == 0) {
                check = 1;
                break;
            }
            else if (arr[j] > sqrt(i)) {
                break;
            }
        }
        if (check == 0) {
            arr[cnt] = i;
            cnt++;
        }
    }
 
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        int l, r;
        scanf("%d%d", &l,&r);
        int answer = 0;
        if (l == 1 || l == 2)
            answer++;
 
        for (int i = 0; i < cnt; i++)
        {
            if (arr[i] > r)
                break;
            if (arr[i] < l)
                continue;
            if (arr[i] % 4 == 1)
                answer++;
        }
        printf("#%d %d\n", test_case, answer);
    }
    return 0;
}