[프로그래머스]소수 찾기 - 파이썬(Python)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

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

---

My Solution

import math
from itertools import permutations

def solution(numbers):
    answer = 0
    numbers = list(numbers)
    items = set(map(int, numbers))
    for i in range(2, len(numbers) + 1):
        for item in list(permutations(numbers, i)):
            items.add(int(''.join(item)))

    m = max(items)
    prime = [True] * (m + 1)
    prime[0] = prime[1] = False
    for i in range(2, int(math.sqrt(m)) + 1):
        if prime[i]:
            j = 2
            while i * j <= m:
                prime[i *j] = False
                j += 1

    for item in items:
        if prime[int(item)]:
            answer += 1

    return answer

 

Key Idea

• items 변수에 가능한 조합 저장
  → itertools.permutations를 이용
• 에라토스테네스의 체를 이용한 소수 판별
  → sqrt(최댓값) + 1 까지 돌면서 소수의 배수를 없애는 방법

 

Best Solution

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

Key Idea

• 전체적인 아이디어는 나의 풀이와 같다.
• range를 이용한 set 구현
• set을 이용해 에라토스테네스의 체를 구현