[python]프로그래머스(level1) - 소수 만들기

0. 문제설명

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

제한사항

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

---

1. code

from itertools import combinations

def solution(nums):
    
    answer = 0
    
    num_set = list(combinations(nums, 3)) #가능한 3개수 조합
    for a, b, c in num_set:
        sum = a + b + c # 3개수의 합
        
        for i in range(2, sum):
            if sum % i == 0:
                break
        else:
            answer += 1

    return answer
    
    from itertools import combinations

def solution2(nums): #소수 제곱근 판별
    
    answer = 0
    
    num_set = list(combinations(nums, 3))
    for a, b, c in num_set:
        sum = a + b + c
        
        for i in range(2, int(sum**(1/2))+1):
            if sum % i == 0:
                break
        else:
            answer += 1

    return answer

---

2. 문제풀이

자료구조

num_set = [(a,b,c)]
nums 리스트에서 가능한 3개의 수의 조합

설명

모든 가능한 3개수 조합의 합에 대해 소수를 판별한다.

---

3. 새로운 사실

다른문제 푸느라 알아놨던 combinations()를 바로 써먹었다.

소수를 구하는 시간복잡도는 똥망이라 분명 어떤 지니어스가 알아낸 것이 있겠지 하고 찾아보니까
에라토스테네스의 접근이 있었다..! 제곱근까지만 확인하면 되는것이었다
에라토스테네스의 체는 소수를 구할때 유용하다지만 이 문제에서는 판별만 하기 때문에 제곱근까지 확인하는 코드로 변경해보니 당연하게도 시간이 많이 단축되었다.
에라토스테네스의 체보다 효율적인 소수구하기 알고리즘이 있다하니 공부를 해봐야할듯 싶다.

4. 주저리 주저리

코테 문제들은 자꾸 잊고지냈던 수학 공식같은걸 찾아보게 만든다ㅋ
수학안한지 너무 오래라 바보가 된것 같다 ^^!!