순열 선물하기

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

요약

1부터 N까지의 정수를 하루에 하나씩 나열하여 매일 누적 합이 소수가 되지 않는 순서를 찾는 문제입니다.

난이도: 보통10점 중 6점
유형: 정수론, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

준원이는 정수 $1,2,\cdots ,N$ 을 가지고 있다. 준원이는 이 정수를 하루에 하나씩, $N$ 일에 걸쳐 현석이에게 선물하려고 한다. 현석이는 소수를 싫어하므로, 현석이가 지금까지 받은 수의 합이 소수가 되는 날이 없어야 한다.

입력

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

출력

현석이를 만족시키면서 정수 $1,2,\cdots ,N$ 을 선물하는 방법이 있다면 첫째 줄에 YES를, 없다면 NO를 출력한다. 방법이 있다면 둘째 줄에 $i$ 번째 날에 선물한 정수가 $i$ 번째 수가 되도록, 선물 순서를 나타내는 정수 $N$ 개를 공백으로 구분하여 출력한다.

예제3

예제 1
입력
```
5
```
예상 출력
```
YES
4 2 3 5 1
```
예제 2
입력
```
2
```
예상 출력
```
NO
```
예제 3
입력
```
1
```
예상 출력
```
YES
1
```