[programmers] 소수 찾기

Link

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

---

Code

from itertools import permutations
import math

def solution(numbers):
    list_numbers = list(numbers)
    pm = set()
    for i in range(1, len(numbers) + 1):
        for x in list(int(''.join(permute)) for permute in permutations(list_numbers, i)):
            pm.add(x)
    mx = max(pm)
    prime = [True for _ in range(mx + 1)]
    prime[0] = False; prime[1] = False
    for i in range(2, int(math.sqrt(mx)) + 1):
        if prime[i]:
            j = 2
            while i * j <= mx:
                prime[i * j] = False
                j += 1
    answer = 0
    for p in pm:
        if (prime[p]):
            answer += 1
    return answer

---

Solution

일단 주어진 숫자의 모든 경우의 수를 구하기위해 permutations에 for문을 이용하여 모든 경우의 수를 구하는데 중복되는 경우가 존재하므로 set에 넣어 중복을 방지한다. 그리고 소수를 판별하기 위해 에라토스테네스의 체를 사용한다. 체의 최대값은 set 값의 최대값으로 설정하고 for문을 돌려 2부터 제곱근까지를 i, j는 2부터 곱하기 i를 할때 mx값이 될때까지 prime 리스트에 False를 넣으면 체를 완성할수 있고 set를 돌면서 소수 판별을 한후 answer를 리턴