문제
병윤이는 합이 소수가 되는 쌍을 찾는 문제에는 질렸다. 이번에는 합이 두 소수의 곱이 되는 쌍을 찾으려고 한다. 양의 정수 $N$이 주어지면 $1$ 이상 $N$ 이하의 정수들 중 합이 어떤 두 소수의 곱이 되도록 하는 두 수의 쌍을 최대한 많이 골라야 한다. 이때 두 소수는 같아도 되며, $1$부터 $N$까지의 수는 각각 최대 한 번만 고를 수 있다.
입력
첫째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100\,000)$
출력
첫째 줄에 조건을 만족하는 쌍의 개수 $K$를 출력한다.
다음 $K$개 줄에 걸쳐 조건을 만족하는 쌍을 출력한다. 각 줄에는 두 정수를 공백으로 구분하여 출력한다. 두 정수의 합은 두 소수의 곱이어야 하고, $1$ 이상 $N$ 이하의 수를 각각 최대 한 번만 출력해야 한다.
조건을 만족하는 쌍이 여러 가지일 경우 그중 아무거나 출력한다.
예제 입력 1
2
예제 출력 1
0
어떤 쌍도 만들 수 없다.
예제 입력 2
3
예제 출력 2
1 1 3
$1 + 3 = 2 \times 2$이다.
$2$쌍 이상을 만들 수 없으므로 $K = 1$이 최대이다.
예제 입력 3
12
예제 출력 3
6 1 9 2 12 3 6 4 11 5 10 7 8
- $1 + 9 = 2 \times 5$
- $2 + 12 = 2 \times 7$
- $3 + 6 = 3 \times 3$
- $4 + 11 = 5 + 10 = 7 + 8 = 3 \times 5$
$7$쌍 이상을 만들 수 없으므로 $K = 6$이 최대이다.
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 07. D번
- 문제를 만든 사람: kiwiyou
- 문제를 검수한 사람: chogahui05, heeda0528, lky7674, pjshwa, snrnsidy, utilforever