완전 탐색 - 소수 찾기

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

일단 라이브러리를 사용해서 조합을 구하는게 제일 첫번째인 것같다.
조합은 itertools에서 permutations을 import하면 사용할 수 있었다.

from itertools import permutations

만약 3개의 숫자가 있으면 1개만 뽑아서 쓰는 조합, 2개만 뽑아서 쓰는 조합, 3개만 뽑아서 쓰는 조합 이렇게 되니까 for문을 돌려 permutations 함수를 써야한다.

permutat = []
    for n in range(1, len(numbers)+1):
        permutat += list(permutations(numbers, n))
        

처음엔 append를 사용했는데 그러면 좀 드럽게 나온다 ㅡㅡ;

그다음은 join함수와 int변환을 통해 곧바로 숫자를 조합해서 정수로 만들도록 한다. 그리고 나선 소수 판별이 관건.

소수 판별이 제일 어렵지않을까 고민했는데 구글링해보니 간단했다.

for문을 돌리면서 2부터 루트(소수판별할 수)까지 나눠지는 경우가 있는지 확인하면 되는 것이다 (%연산자를 통해 0이면 나눠지니까 바로 소수가 아니니 False)

근데 왜 범위가 루트로 씌워서 할까?
일단 계산의 복잡도를 줄이기 위해서라는건 알겠다.
하지만 루트를 씌우면 모든 경우의 수를 고려할 수 있을까?

예를 들어 17를 생각해보자.
17은 1, 17으로만 약수가 나오기때문에 소수.

[9]
1 3 9
19 = 9
33 = 9

[10]
1 2 5 10
110 = 10
25 = 10
어차피 대칭이라는 특징을 갖고있으니까 반절만 보면 그만이라는 것.
그니까 루트를 잘 사용하자.

루트를 잘 쓸일이 없어 헷갈리니 좀 더 정리하다
math 라이브러리를 불러와야하고 sqrt함수를 사용하면 된다.

최종 코드다.

import math
from itertools import permutations

# 소수인지 판별
def prime(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    permutat = []
    for n in range(1, len(numbers)+1):
        permutat += list(permutations(numbers, n))
    permutat = [int(("").join(p)) for p in permutat]
    permutat = list(set(permutat))
    
    ct = 0
    for num in permutat:
        if num == 0 or num == 1:
            continue
        if prime(num):
            ct += 1
    return ct