[PRO] 소수 찾기 (Python) [알고리즘 고득점 Kit]

완전탐색에 해당하는 문제이다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839

풀이

itertools의 permutations를 이용하여 모든 경우의 수를 쉽게 구할 수 있다.
또한, 소수인지 판정할 때 root까지만 탐색해도 되는 점을 이용했다.

from itertools import permutations
from math import sqrt


def is_sosu(n):
    """소수이면 True 반환"""
    for i in range(2, int(sqrt(n))+1):
        if n%i==0:
            return False
    return True


def solution(numbers):
    answer_set = set()
    
    for num_len in range(1,len(numbers)+1):
        for p in permutations(numbers, num_len):
            check_num = int(''.join(p))
            # 0,1은 제거
            if check_num >1 and is_sosu(check_num): # 소수인지 판단 & 소수set에 추가
                answer_set.add(check_num)
    
    return len(answer_set)