[프로그래머스/파이썬] 완전탐색 소수 찾기

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

---

알고리즘 분류

• 브루트포스

문제풀이

입력받은 numbers에서 각 글자를 분리해서 순열리스트를 만들어준다.

그리고 순열리스트에서 문자열을 합쳐주고 다 합쳐지면 정수형으로 lst에 넘겨주었다.

그 후 set자료형을 통해 중복값을 제거해주고 소수에 해당하는 값만 result결과에 넘겨주면 정답이다.

여기서 소수인지를 확인하는 check함수의 경우, 0과 1은 소수가 아니므로 false를 반환하고, 소수를 판단하는 공식에 의해 소수가 아니라면 역시 false를 반환, 마지막엔 소수만 남으므로 true를 반환해준다.

2≤p≤√n인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다.

출처: https://terms.naver.com/entry.nhn?docId=1113970&cid=40942&categoryId=32206

소스코드

def solution(numbers):
    from itertools import permutations
    import math
    num=[i for i in numbers]

    array=[]
    for i in range(1,len(num)+1):
        array+=list(permutations(num,i))

    lst=[]
    for i in array:
        temp=''
        for j in range(len(i)):
            temp+=i[j]
        lst.append(int(temp))
    set_array=set(lst)
    def check(x):
        if x<2:
            return False

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

    result=[]
    for i in set_array:
        if check(i):
            result.append(i)
    return len(result)