[완전탐색]소수 찾기

더 많은 코드 (https://github.com/EunGyeongKim/TIL)

GitHub - EunGyeongKim/TIL: Today I Learne

문제 링크

프로그래머스

1. 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

---

2. 제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

---

3. 입출력 예

numbers	return
"17"	3
"011"	2

---

4. 코드

import itertools
import math
def solution(numbers):
    answer = 0

    numbers = list(numbers)
    n_list = []

    # 순열 조합 추가
    for i in range(1, len(numbers)+1):
        tmp = list(itertools.permutations(numbers, i))
        for j in tmp:
            n_list.append(int("".join(j)))

    # 중복제거
    n_list = set(n_list)

    def find_prime(x):
        if x == 1 or x == 0:
            return False
        # 2부터 x의 제곱근까지의 모든 수를 확인하며
        for i in range(2, int(math.sqrt(x)) + 1):
            # x가 해당 수로 나누어떨어진다면
            if x % i == 0:
                return False # 소수가 아님
        return True # 소수임

    # 소수갯수 세기
    for i in n_list:
        if find_prime(i):
            # print(i)
            answer += 1

    return answer