28708번 - 소수 피하기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 111 | 49 | 42 | 54.545% |
문제
$N$개의 양의 정수 $A_1, \cdots, A_N$이 주어집니다. 당신의 목적은 모든 $1 \le i < j \le N$에 대해서 $A_i + A_j$가 소수가 아니도록 만드는 것입니다.
이를 위해 당신은 다음 조작을 정확히 $1$번 할 수 있습니다.
- $1$ 이상 $N$ 이하의 서로 다른 $K$개의 정수 $i_1, i_2, \cdots, i_K$를 고릅니다. $A_{i_1}, A_{i_2}, \cdots, A_{i_K}$에 각각 $1$을 더합니다. $(0 \le K \le N)$
모든 $1 \le i < j \le N$에 대해서 $A_i + A_j$가 소수가 아니도록 하는 조작에서 $K$의 최솟값을 출력하세요.
입력
첫 줄에 수의 개수 $N$이 주어집니다. $(2 \le N \le 200)$
둘째 줄에 $A_1, \cdots, A_N$이 공백으로 구분되어 주어집니다. $(1 \le A_i \le 1\,000\,000)$
출력
모든 $1 \le i < j \le N$에 대해서 $A_i + A_j$가 소수가 아니도록 하는 조작의 $K$의 최솟값을 출력하세요.
$K \ne 0$인 경우, 둘째 줄에 고른 $i_1, i_2, \cdots, i_K$를 공백으로 구분하여 출력하세요. 정답이 여럿인 경우 아무거나 출력해도 좋습니다.
예제 입력 1
6 3 1 4 1 5 9
예제 출력 1
5 1 2 4 5 6
예제 입력 2
10 30 41 66 70 104 110 153 165 231 385
예제 출력 2
3 5 7 2
예제 입력 3
6 2520 2521 2522 2523 2524 2525
예제 출력 3
0
출처
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호