골드바흐의 추측

면접 대비

시간 제한1초메모리 제한128 MB

요약

2^15 미만의 짝수 n마다 합이 n이 되는 순서 없는 소수 쌍의 개수를 세고, 0이 나오면 입력을 끝낸다.

난이도: 쉬움10점 중 3점
유형: 정수론, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

4 이상의 모든 짝수 $n$ 은 두 소수 $p_1$ , $p_2$ 의 합으로 나타낼 수 있다는 추측이 있습니다.

$n = p_1 + p_2$

이 추측은 아직 증명되지도, 반증되지도 않았습니다. 하지만 주어진 짝수에 대해 조건을 만족하는 소수 쌍이 존재하는지, 존재한다면 몇 개인지는 직접 찾아볼 수 있습니다.

여러 개의 짝수가 입력으로 주어집니다. 각 짝수마다 위 조건을 만족하는 소수 쌍의 개수를 출력하는 프로그램을 작성하세요. 단, 본질적으로 서로 다른 쌍의 개수만 세어야 합니다. 즉 $(p_1, p_2)$ 와 $(p_2, p_1)$ 은 같은 쌍으로 보고 한 번만 셉니다.

입력

각 줄에 정수가 하나씩 주어집니다. 모든 정수는 짝수이며 $4 \le n < 2^{15}$ 을 만족합니다. 입력의 끝은 숫자 $0$ 으로 표시됩니다.

출력

각 짝수에 대해 조건을 만족하는 소수 쌍의 개수를 한 줄에 하나씩 출력합니다. 그 외의 다른 문자는 출력하지 않습니다.

예제4

예제 1
입력
```
6
10
12
0
```
예상 출력
```
1
2
1
```
예제 2
입력
```
8
0
```
예상 출력
```
1
```
예제 3
입력
```
100
0
```
예상 출력
```
6
```
예제 4
입력
```
1000
0
```
예상 출력
```
28
```