[프로그래머스] 소수 찾기

출처:: programmers.co.kr/learn/courses/30/lessons/42839

분류:: 완전탐색 

 

1. 문제 이해 및 해결과정

  1.

1) 소수를 미리 찾아놓음 2) 입력받은 수에서 가능한 모든 경우 찾아둠 3) 가능한 수가 소수면 개수 count

 

 

2. 풀이방법

  1. 에라토스테네스의 체 + 순열 

import math
from itertools import permutations
def solution(numbers):
    cnt=0
    max=10000000
    #소수를 미리 찾아놓음 - 에라토스테네스의체 이용
    prime=[True]*max
    prime[0],prime[1]=False,False
    for i in range(2,int(math.sqrt(max))+1):
        j=2
        if prime[i]:
            while i*j<max:
                prime[i*j]=False
                j+=1
    leng=len(numbers) 
    selected=[]
    for i in range(1,leng+1):
        arr=permutations(numbers,i) #될 수 있는 모든 경우 찾기 
        for x in arr:
            selected.append(int(''.join(x)))
            
    selected=set(selected) #중복제거 

    for x in selected:
        if prime[x]:#소수일 경우 count 
            cnt+=1
 
    return cnt

 

3. 오답원인

 

4. 알게된 점