프로그래머스 - 소수 찾기 [파이썬]

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

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

---

풀이 과정

numbers 문자열의 각 문자로 몇 개의 소수를 만들 수 있는지 반환해줘야 한다.

 

나올 수 있는 최대 수까지 에라토스테네스의 체를 사용해 소수를 미리 구해준 후, numbers의 각 문자로 만들 수 있는 모든 숫자의 쌍을 permutations 모듈을 이용하여 구해주었다. 그 후, 숫자가 소수면 정답 후보 리스트에 넣고, 정답 후보 리스트를 set으로 바꿔줬다가 list로 바꿔줘서 중복을 제거한 후, 리스트의 원소의 개수를 리턴하여 답을 구하였다.

---

소스 코드

from itertools import permutations


def solution(numbers):
    max_number = 10000001
    check = [False for _ in range(max_number)]
    check[0], check[1] = True, True
    
    for i in range(2, max_number):
        if not check[i]:
            for j in range(2*i, max_number, i):
                check[j] = True
                
    numbers = list(str(numbers))
    number_list = []
    
    for i in range(1, len(numbers) + 1):
        for j in permutations(numbers, i):
            temp = int(''.join(j))
            if not check[temp]:
                number_list.append(temp)
    
    return len(list(set(number_list)))