[자료구조] 세 소수의 합 파이썬 (prime number)

from itertools import combinations


def check(n):
    k = n**0.5
    if n < 2: 
        return False

    for i in range(2, int(k)+1):
        if n % i == 0:
            return False
    return True

def solution(n):
    candidates = []
    for i in range(2,n+1):
        if check(i):
            candidates.append(i)
            
    combi = combinations(candidates, 3)
    
    ans = 0
    for c in combi:
        if sum(c) == n:
            ans += 1
    return ans
    

2부터 n까지의 수 중에서 소수인 경우만 candidates 리스트로 저장

 

combinations 사용해서 가능한 모든 조합 중에서 sum == n을 만족할 경우만 cnt +1

 

combinations 때문에 효율성 통과 못할 수 있다고 생각했는데

 

통과하긴 했지만

 

저기서 더 효율적인 방법을 찾아야할듯.

---

일단은 candidates 까지는 바꿀건 없고

 

조합을 찾는 부분에서 줄이는게 가능할 것 같은데.