손가락놀이터

문제 후기

처음 보자마자 조합과 소수 구하기를 적용해야 풀어야 한다고 생각했습니다. 조합의 경우 itertools의 combination보다 코드로 구현하는 것이 더 빨라 코드로 구현하였습니다.

소수 구하기 경우 에라토스테네스의 체를 이용하여 시간을 단축시켰습니다.

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

from math import sqrt

def solution(nums):
    answer = 0  # 정답값

    for one in range(len(nums)-2):  # 첫번째 숫자
        for two in range(one+1, len(nums)-1):   # 두번째 숫자
            for three in range(two + 1, len(nums)): # 세번째 숫자
                chk_num = nums[one] + nums[two] + nums[three]   # 숫자의 합
                prime = True    # 소수 판별

                if chk_num % 2 == 0 or chk_num % 3 == 0 or chk_num % 5 == 0:    # 2,3 5의 배수인 경우 패스
                    prime = False
                else:
                    # 에라토스테네스의 체 적용
                    for factor in range(2, int(sqrt(chk_num)))+1:
                        if chk_num % factor == 0:
                            prime = False
                            break
                        else:
                            pass
                if prime:
                    # 소수인 경우 정답 + 1
                    answer += 1

    return answer