PROGRAMMERS 소수 찾기

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

input :

• numbers

output :

• numbers의 숫자로 만들 수 있는 소수의 개수를 출력하시오.

조건 :

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

---

idea

주의

• 에라토스테네스의 체를 수행할 때 root를 이용해서 한다면 해당 값 또한 포함되어야 한다.
• 팩토리얼과 같은 수열을 다 수행하기 위해서는 재귀 함수를 사용하는 것이 좋다.

def solution(numbers):
    targets = set()
    def factorial(data, used, string):
        if len(string) > 0:
            targets.add(int(string))
        for key in data.keys():
            if data[key] == used[key]:
                continue
            used[key] += 1
            factorial(data, used, string + key)
            used[key] -= 1
    
    data, used = dict(), dict()
    for item in numbers:
        if item not in data:
            data[item] = 0
            used[item] = 0
        data[item] += 1
    factorial(data, used, "")
    
    data = list(targets)
    cnt = 0
    for item in data:
        if item < 2:
            continue
            
        flag = 1
        for comp in range(2, int(item ** (1 / 2) + 1)):
            if item % comp == 0:
                flag = 0
                break
        
        if flag:
            cnt += 1
    return cnt