[프로그래머스 코딩테스트] lv1. 소수 구하기

문제 설명

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

나의 풀이

from itertools import combinations

def solution(nums):
    combi = list(combinations(nums,3))
    answer = len(combi)
    sums = []
    for c in combi:
        for i in range(2, sum(c)+1):
            if (sum(c) % i == 0):
                if i != sum(c):
                    answer -= 1
                    break

    return answer

저는 sum(c) 까지의 모든 수를 나눠보는 코드를 작성해 시간이 매우 오래 걸렸습니다. 다른 사람들의 풀이를 보니 '에라토스테네스의 체' 방식을 이용하면 더 빠르게 결과를 낼 수 있다는 것을 알게 되었습니다. 이 방식을 이용한 풀이는 다음과 같습니다.

from itertools import combinations

# 에라토스테네스의 체
def is_prime(n):
    divisor = 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisor += 1

    return True if divisor == 0 else False

def solution(nums):
    return [is_prime(sum(c)) for c in combinations(nums,3)].count(True)

 

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12977