소수 만들기 / 프로그래머스

 

접근방법

특정 길이의 리스트에서 3가지의 수를 뽑는 모든 경우의 수 구하기

백트래킹

1. 첫 번째 숫자를 고정하고,
2. 두 번째 숫자를 첫 번째 숫자 이후의 값 중에서 선택,
3. 세 번째 숫자를 두 번째 숫자 이후의 값 중에서 선택하여,
4. 모든 경우의 수를 탐색하는 방식으로 구현

소수를 구할 때는 범위를 √n까지만 확인하면 된다!

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):  # √n까지만 확인
        if n % i == 0:
            return False
    return True

 

정답

import itertools
def solution(nums):
    answer = 0
    num = list(itertools.combinations(nums, 3))
    for i in num:
        isPrime = 0
        k = sum(i)
        for j in range(2, k):
            if k % j == 0:
                isPrime = 1
                break
        if isPrime == 0:
            answer = answer + 1
    return answer