블로그 이사 중입니다 >> gumgood.github.io

1153 네 개의 소수 본문

Problem Solving/문제 풀이

1153 네 개의 소수

gumgood 2019. 1. 15. 13:48

'골드바흐의 추측'에 근거한 풀이이다.


네 개의 소수로 표현할 수 있는 가장 작은 수는 $8 (2+2+2+2)$이다.


8이상의 $n$에 대해

$n$이 짝수인 경우, $n-4$를 두 소수 $p1$, $p2$의 합으로 표현해주면 답은 다음과 같다.

 $n = 2 + 2 + p1 + p2$

$n$이 홀수인 경우, $n-5$를 두 소수 $p1$, $p2$의 합으로 표현해주면 답은 다음과 같다.

 $n = 2 + 3 + p1 + p2$


어떤 2이상의 짝수 $n$를 두 소수의 합으로 표현하는 것은 전처리를 포함해 $O(n)$이 걸린다.

'Problem Solving > 문제 풀이' 카테고리의 다른 글

14891 톱니바퀴  (0) 2019.01.17
14503 로봇 청소기  (0) 2019.01.17
1153 네 개의 소수  (0) 2019.01.15
3163 떨어지는 개미  (0) 2018.12.26
6064 카잉 달력  (0) 2018.11.13
2903 중앙 이동 알고리즘  (0) 2018.11.13
0 Comments
댓글쓰기 폼