[코딩테스트] 완전탐색 - 소수 찾기

 

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

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

 

[ 내 풀이 ]

# 소수판별함수
from itertools import permutations

def check(num):
    if num<=1:
        return False
    
    for i in range(2, (num//2)+1):
        if num%i==0:
            return False
    
    return True

def solution(numbers):
    answer = 0
    cand = []
    
    for i in range(len(numbers)):
        temp = list(map("".join, permutations(numbers, i+1)))
        cand.extend(temp)
        
    cand = list(set((map(int, cand))))
    
    for candidate in cand:
        if check(candidate)==True:
            answer +=1
            
    return answer

 

흐름은 같은데 에라토스테니스의 체를 이용한 기막힌 풀이가 있었다.

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)

set을 활용해서 좀 더 간단하게 후보군 집합을 만들고,

소수를 찾는 알고리즘인 에라토스테네스의 체의 방식으로 소수가 아닌 후보들을 빼준다.