[프로그래머스] 완전탐색 - 소수 찾기 (Python)

코딩테스트 연습 - 소수 찾기

def is_prime(x):
    import math
    if x<2: return False
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0: return False
    return True

from itertools import permutations
def solution(numbers):
    array = []
    for i in range(1, len(numbers)+1) :
        temp = list(permutations(list(numbers), i))
        temp = ["".join(j) for j in temp]
        array.extend(temp)
    array = set(map(int, array))
    array = [is_prime(i) for i in array]
    
    answer = sum(array)
    return answer

 우선 에라토스테네스의 체를 이용하여 is_prime 함수를 생성해준다. 소수인지 확인하기 위해서는 그 값의 루트 값까지의 숫자들로만 나누어주면 된다는 정수론의 유명한 정리다.

 그 다음 모든 원소들로 경우의 수를 만들고자 했기에 permutation을 사용해준다. 나온 결과를 join을 이용하여 결합, 011와 11을 구분하기 위해 map으로 int형으로 변형, set으로 중복된 원소들을 제거해줌으로써 시간 단축

 이 과정을 거치면 어렵지 않게 문제가 해결 가능하다.