Programmers Summer/Winter Coding(~2018)소수 만들기 파이썬

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) , 코딩테스트 연습 - 소수 만들기 | 프로그래머스 (programmers.co.kr)

주어진 배열 속에서 숫자 3개를 뽑아서 만들 수 있는 소수의 개수를 찾는 문제. 

크게 2파트로 나뉜다. 

1. 숫자 3개 뽑아 더하기

2. 소수 판별

소수를 판별하는데는, 가장 효율적인 방법인 에라토스테네스의 체를 활용했다. 

숫자 3개를 뽑아 더하는것에 있어서는, 배열 속 중복된 수가 없다는점과, 비복원추출의 방법을 사용해야하므로, 
combinations 를 사용했다.

from itertools import combinations
def solution(nums):
    def mknum(n):
        arr=[i for i in range(n+1)]
        
        for i in range(2,(n//2)+1):
            # print(arr)
            if arr[i]<2: continue
            else:
                cnt=2
                while i*cnt < len(arr):
                    # print(i*cnt)
                    arr[i*cnt]=0
                    cnt+=1
        return [i for i in arr[2:] if i!=0]
    
    arr=mknum(max(nums)*3)
    numlist=list(map(lambda x : sum(x), list(combinations(nums,3))))
    answer=0
    for n in numlist:
        if n in arr:
            answer+=1

    return answer
solution([1,2,7,6,4])