소수 찾기

• 그냥 무식하게 모든 가능한 숫자들을 다 만들어본다. itertools.permutation을 쓰면 간단하다. O(n!)개의 숫자들이 만들어진다.
• 어떤 수 m이 소수인지 체크하는 것은 sqrt(m)까지로 다 나눠보면 되므로 O(sqrt(m))에 가능하다. m의 범위는 O(10^n)이다.
• 결국 전체 시간 복잡도는 O(n!*10^(n/2)). 무시무시해보이지만 n≤7이라서 별 문제 없다.
• O(n!)개의 수 중에서 중복되는 수를 한번만 카운트해야 하므로 set을 써서 중복을 제거하는 과정을 빼먹지 말것.

"""Solution code for "Programmers 42839. 소수 찾기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42839
- Solution link: http://www.teferi.net/ps/problems/programmers/42839
"""

import itertools
import math


def is_prime(num):
    return (num >= 2 and
            all(num % i != 0 for i in range(2, math.isqrt(num) + 1)))


def solution(numbers):
    nums = set()
    for i in range(1, len(numbers) + 1):
        nums.update(int(''.join(x)) for x in itertools.permutations(numbers, i))
    return sum(1 for num in nums if is_prime(num))