James Ferraro - Live at Primavera Sound 2012

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

요약

1부터 N까지의 수를 각각 최대 한 번씩 사용해 두 수의 합이 두 소수의 곱이 되도록 최대한 많은 쌍을 만든다.

난이도: 어려움10점 중 8점
유형: 정수론, 그리디, 수학, 그래프
정답자: 아직 제출이 없습니다

문제

병윤이는 합이 소수가 되는 쌍을 찾는 문제에는 질렸다. 이번에는 합이 두 소수의 곱이 되는 쌍을 찾으려고 한다. 양의 정수 $N$ 이 주어지면 $1$ 이상 $N$ 이하의 정수들 중 합이 어떤 두 소수의 곱이 되도록 하는 두 수의 쌍을 최대한 많이 골라야 한다. 이때 두 소수는 같아도 되며, $1$ 부터 $N$ 까지의 수는 각각 최대 한 번만 고를 수 있다.

입력

첫째 줄에 정수 $N$ 이 주어진다. $(1 \le N \le 100\\,000)$

출력

첫째 줄에 조건을 만족하는 쌍의 개수 $K$ 를 출력한다.

다음 $K$ 개 줄에 걸쳐 조건을 만족하는 쌍을 출력한다. 각 줄에는 두 정수를 공백으로 구분하여 출력한다. 두 정수의 합은 두 소수의 곱이어야 하고, $1$ 이상 $N$ 이하의 수를 각각 최대 한 번만 출력해야 한다.

조건을 만족하는 쌍이 여러 가지일 경우 그중 아무거나 출력한다.

예제3

예제 1
입력
```
2
```
예상 출력
```
0
```
예제 2
입력
```
3
```
예상 출력
```
1
1 3
```
예제 3
입력
```
12
```
예상 출력
```
6
1 9
2 12
3 6
4 11
5 10
7 8
```