[Algorithm] [Python] Programmers - 세 소수의 합

Programmers - 세 소수의 합

 

문제 설명

---

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

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

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

 

제한 조건

---

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

 

입출력 예

---

• n: 33 , return: 4
• n: 9 , return : 0

 

제출 코드

---

from itertools import combinations

# n을 전달받아서 n보다 작은 소수 리스트 구하기
def getPrimeList(n):
    sieve = [True] * n         

    for i in range(2, int(n**0.5) + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

def solution(n):
    result = 0
    primeList = getPrimeList(n)
    for candidate in list(combinations(primeList, 3)):
        if sum(candidate) == n:
            result += 1

    return result

 

코드 설명

---

문제는 주어진 정수 n을 서로 다른 소수의 수 3개로 표현이 가능한 경우의 수를 반환해야 한다.

3개의 소수를 조합하여 n을 만들기 위해서는 당연히 n보다 작은 소수들로 구성된 리스트가 필요하다.

따라서, 소수를 구함에 있어 자주 사용되는 개념인 에라토스테네스의 체 를 이용하여 n보다 작은 소수 리스트를 구하였다.

이후 itertools 의 combinations 를 이용하여 해당 리스트로 부터 3개의 숫자 조합의 합이 n과 같은지 비교하는 방식으로 구현하였다.