[프로그래머스/Python] 소수찾기(완전탐색)

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

 

from itertools import permutations

def isPrime(n, dp):
    max_length = int(n**0.5)
    for i in range(2, max_length+1):
        if dp[i] == True:
            for j in range(i*i, n+1, i):
                dp[j] = False
    return dp

def solution(numbers):
    answer = 0
    
    a = []
    for i in range(1,len(numbers)+1):
        a += list(permutations(numbers,i))
            
    
    last = []
    for i in a:
        string = ""
        for j in i:
            string += j
        last.append(int(string))
    last= set(last)
    
    dp = isPrime(max(last), [False, False]+[True]*(max(last)-1) )

    for i in last:
        if dp[i]:
            answer += 1
    
    return answer