어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 구하려 합니다. 예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

  • 3+7+23
  • 3+11+19
  • 3+13+17
  • 5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 return 하는 solution 함수를 작성해주세요.

제한 조건

  • n은 1,000 이하인 자연수입니다.

입출력 예

n return
33 4
9 0

나의 풀이

  • 에라토스테네스의 체로 n의 소수를 모두 구한다.
  • 소수 리스트에서 itertools.combinations을 사용해 조합을 구한다.
from itertools import combinations

def solution(n):
    # 에라토스테네스의 체로 n의 소수 구하기
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i]:
            for j in range(i+i, n, i):
                sieve[j] = False
    prime = [i for i in range(2, n) if sieve[i]]
    
    cnt = 0
    result = list(combinations(prime, 3))
    for r in result:
        if sum(r) == n:
            cnt += 1
            
    return cnt