프로그래머스 소수 찾기

아이디어:

numbers 배열에서 만들 수 있는 모든 정수를 구한 후 소수인지 판별(dfs) -> 소수라면 temp에 저장

import math

temp = []
def solution(numbers):
    iniarr = list(map(int, numbers))
    for i in range(1, len(iniarr)+1):
        dfs(i, iniarr)
    print(temp)
    answer = len(temp)
    return answer

def dfs(m, numbers, arr =[], visited = []):
    if len(arr) == m :
        num = 0
        for j in range(0, m):
            num += 10 ** (m-j-1) * arr[j]
        if num not in temp and isPrime(num)==True:
            temp.append(num)
        return
    else:
        for i in range(0,len(numbers)):
            if i not in visited:
                visited.append(i)
                arr.append(numbers[i])
                dfs(m, numbers, arr)
                arr.pop()
                visited.pop()
                
def isPrime(num):
    if num <= 1:
        return False
    if num == 2:
        return True    
    for i in range(2, int(math.sqrt(num))+1):
        if (num % i) == 0:
            return False
    return True

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전