[프로그래머스 코딩테스트]Level 01 - 세 소수의 합

Level 01 - 세 소수의 합

문제 설명

본 문제는 에라토스테스트의 체 알고리즘을 이용해서 풀어주세요.
어떤 수를 서로 다른 소수 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

대표적인 소수 구하는 알고리즘인 “에라스토테네스의 체”

from itertools import combinations

def prime(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

def solution(n):
    answer = 0
    prime_list = prime(n) # n보다 작은 소수들의 리스트를 구한다
    # 소수 리스트에서 3개의 수로 만들 수 있는 조합을 구한다.
    prime_combi = list(combinations(prime_list, 3))
    for i in range(len(prime_combi)):
        if sum(prime_combi[i]) == n:# 조합의 합이 n이라면 +1
            answer += 1
    return answer