문제

풀이 과정

문제의 페르마 식은 다음과 같다.

어떤 소수 $P$ 가 어떤 수 $x^2+y^2$ 로 나타 낼 수 있다면, 이는 $P$ 는 4로 나누었을 때 나머지는 1이다.

단 이 공식에는 허점이 존재한다. 왜냐면 $2=1^2+1^2$ 이 가능하기 때문이다.

웃너 배열 최대 범위 안에서 소수를 모두 찾는다. 여기에서는 에라토스테네스의 체를 사용하였다.

다음 $L$ 과 $U$ 범위 만큼 소수 갯수와 페르마의 식에 성립되는 소수 갯수를 구한다.
$L$, $U$ 가 음수가 나올 수도 있는데, 음수는 소수가 아니므로, 0 부터 시작하면 된다.

소수란 1과 자기 자신만으로 나누어 떨어져야 하는데, 1은 양의 정수이므로 음수는 소수가 될 수 없다.

정답

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static final int INF = 1000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // false -> 소수
        // true -> 소수 아님
        boolean[] primeN = new boolean[INF];
        primeN[0] = true;
        primeN[1] = true;
        for (int i = 2; i < INF; i++) {
            if (!primeN[i]) {
                for (int j = i + i; j < INF; j += i) {
                    if (primeN[j]) continue;
                    if (j % i == 0) primeN[j] = true;
                }
            }
        }

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int U = Integer.parseInt(st.nextToken());

            if (L == -1 && U == -1) break;

            int tempL = L<0 ? 0 : L;
            int tempU = U<0 ? 0 : U;
            int x = 0;
            int y = 0;


            for (int i = tempL; i <= tempU; i++) {
                if (!primeN[i]) {
                    if (i % 4 == 1 || i == 2) y++;
                    x++;
                }
            }

            bw.write(L + " " + U + " " + x + " " + y);
            bw.append("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}