[프로그래머스] 세 소수의 합 python

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

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

제한 조건
n은 1,000 이하인 자연수입니다.

에라토스테네스의 체 알고리즘

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11²>120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
출처 : 위키백과

n 이하의 소수를 찾기 위해서 2부터 ceil(sqrt(n)) 이하 소수의 배수를 지워서 소수만 걸러낸다.
combinations를 사용해 n 이하의 소수 3개의 합이 n이 되는지 검사하고 카운트한다.

import math
from itertools import combinations
def solution(n):
    check = [False, False] + [True]*(n-1)
    for i in range(2, math.ceil(n**0.5)):
        for j in range(i*2, n+1, i):
            check[j] = False
    pn = [i for i in range(2,n) if check[i] == True]
    comb = combinations(pn, 3)
    cnt = 0
    for c in comb:
        if sum(c) == n:
            cnt += 1
    return cnt