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

<문제 링크>

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

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

---

<문제 풀이>

1. 종이 조각으로 여러 개의 조합을 만들어야 하므로 itertools 라이브러리 사용
2. 중복된 숫자가 나올 수 있으므로 set() 사용
3. 소수는 에라토스테네스의 체 공식으로 찾음

<코드>

from itertools import permutations
from math import sqrt

def solution(numbers):
    s = set()
    for i in range(1,len(numbers)+1):
        for a in permutations(numbers,i):
            s.add(a)
    li = set(map(''.join,s))
    li2 = set(map(''.join,s))
    li = set(map(int,li))
    li2 = set(map(int,li))
    for i in li:
        if i==1 or i==0:
            li2.remove(i)
        else:
            for k in range(2,int(sqrt(max(li)))+1):
                if i%k==0 and i!=k:
                    li2.remove(i)
                    break
    return len(li2)

 

<고쳐야 할 점>

• from itertools import permutations 메서드 기억하기
• 에라토스테네스의 체(2~ x 루트값의 범위에 있는 값을 x로 나누었을 때 나누어 떨어지지 않으면 소수) 기억하기
• 제곱근 함수(sqrt) 기억하기