[프로그래머스/Python] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3

프로그래머스

---

문제 유형

• 완전탐색

문제

한자리 숫자가 적힌 종이 조각이 흩어져 있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예제

numbers	return
"17"	3
"011"	2

예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.

---

풀이

1. 문자열을 받아서 → 순열로 바꿔야됨
2. 그런데 그 순열의 길이가 모든 경우에 대해서(완전탐색임)
3. 11과 011과 같은 경우는 같은 숫자로 취급하니 만약 소수인 경우는 이 케이스는 제외해줘야 함
4. 소수 판별 필요 → 에라토스테네스의 체 이용

---

코드

import math
from itertools import permutations

def solution(numbers):
    answer = 0
    unique = set()
    li_num = list(numbers)

    for i in range(1, len(numbers) + 1):
        for perm in permutations(li_num, i): # 순열로 변환, 완전 탐색
            num = int(''.join(perm))
            if num not in unique and is_p(num): # 11,011 같은 경우 제거 위함
                unique.add(num)
                answer += 1

    return answer

def is_p(x): # 에라토스테네스의 체
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

---