On.

---

Algorithm

---

1. 수도코드

0) 문제 유형 파악: 완전 탐색 문제

1) prime이라는 n 이하의 소수 리스트 생성 -> [2, 3, 5, 7 ...]

• 0부터 n까지의 index를 가진, 원소의 값이 전부 True인 리스트를 생성
• 소수가 아닌 값들은 False로 처리
• 2부터 n의 제곱근까지 i에 할당하여 아래와 같은 곱셈을 반복한다
  • n을 넘어가지 않을때까지만 2부터 1씩 증가시키며 i에 곱한다.
• 곱해서 나온 값은 소수가 아니므로 prime[i*j]는 False처리 (index의 배수기 때문)

2) Combination으로 세가지 숫자 조합 만들기

3) 각각의 조합들의 합을 구함

4) 합을 key로 가지는 Counter 딕셔너리 생성

5) Counter딕셔너리[n] 으로 세 소수의 합이 n인 것의 개수를 리턴

2. 구현코드

import math
from itertools import combinations
from collections import Counter

def solution(n):
    prime = [True for _ in range(n+1)]
    
    for i in range(2, int(math.sqrt(n)) + 1):
        j = 2
        while i * j <= n:
            if prime[i*j]:
                prime[i*j] = False
            j += 1
    prime = [i for i in range(len(prime)) if prime[i]][2:]
    
    return Counter(map(sum, combinations(prime, 3)))[n]

---

Off.

---

프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥