[Python] 프로그래머스 Lv.2 - 소수 찾기

[ 알고리즘 ]

완전탐색,구현

 

[문제 접근]

주어진 numbers로 만들 수 있는 순열을 구해서 ( [1,2], [2,1] 은 다른 것임 ) 소수를 구할 땐 효율성을 위해 에라토스테네스의 체를 이용하여 구현하였다

 

 

[코드]

from itertools import permutations
def solution(numbers):
    answer = 0
    n=len(numbers) #문자열
    num=list(numbers) #리스트
    result=[]
    
    #해당 숫자 조합으로 만들 수 있는 모든 숫자 조합
    List=[]
    for i in range(1,n+1):
        List.append(set(permutations(num,i)))
        
    #체를 이용하여 해당수로 만들 수 있는 최댓값까지의 소수들 찾기
    num.sort(reverse=True)
    Max=''.join(map(str,num))
    Max=int(Max)
    
    find=[0]*(Max+1)
    find[0]=1
    find[1]=1
   
    for i in range(2,int(Max**(0.5))+1):
        if find[i]==0: #안지워진 소수이면
            for j in range(2*i,Max+1,i):
                find[j]=1 #배수들 모두 지움
                
    
    #소수인지 찾아주기
    for i in range(len(List)):
        L=List[i]
        for j in L: 
            j=int(''.join(j))
            if find[j]==0:
                result.append(j)
                
    return len(set(result))