Lv1 세 소수의 합

문제

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

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

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

제한 조건

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

입출력 예

nreturn
334
90

입출력 예 설명

  • 예시 #1
    문제에 나온 예와 같습니다.

  • 예시 #2
    9는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.

풀이

에라토스테스의 체로 소수를 판별하고, combinations 라이브러리를 활용하여 조합을 구한다.

코드

from itertools import combinations
def solution(n):
    answer = 0
    #수와 인덱스를 맞추기 위해서 1개 더함.
    numbers = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        j = 2
        while i*j <= n:
            numbers[i*j] = False
            j += 1
    prime_number = [i for i,j in enumerate(numbers) if i > 1 and j == True]
    cp = list(combinations(prime_number,3))
    for i,j,k in cp:
        if i+j+k == n:
            answer += 1
    return answer

좋은 웹페이지 즐겨찾기