사용한 알고리즘
- 에라토스테네스의 체 (소수 찾기)
풀이 로직
- 소수 = 2 3 5 7 11 13 17 19 23 29,,
- 1부터 직접 해본 결과 8부터 4개의 소수로 표현할 수 있다.
- 8 = 2 + 2 + 2 + 2 / 9 = 2 + 2 + 2 + 3 => 2 + 3 + 2+ 2
- n이 8이상이고 n % 2 == 0이면 '2 2'로 시작한다. -> n -= 4
- n이 8이상이고 n % 2 == 1이면 '2 3'으로 시작한다. -> n -= 5
- 새로 갱신된 n을 기준으로 에라토스테네스의 체를 이용해 n보다 작은 소수를 찾는다.
코드
'알고리즘' 카테고리의 다른 글
| [LEETCODE] 542. 01 Matrix (0) | 2021.01.09 |
|---|---|
| [SWEA] 3462. 선표의 축구 경기 예측 (0) | 2021.01.06 |
| [PROGRAMMERS] 최고의 집합 (0) | 2021.01.04 |
| [BAEKJOON] 4915. 친구 네트워크 (0) | 2021.01.02 |
| [알고리즘] disjoint-set(union find) 알고리즘 (0) | 2021.01.01 |
