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

문제바로가기

from itertools import permutations

def is_prime_naive(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    numbers = list(numbers)
    # numbers = list(map(int, numbers))
    
    num_set = set()
    for i in range(1, len(numbers)+1):
        for p in permutations(numbers, i):
            num = int(''.join(p))
            num_set.add(num)
    
    for n in num_set:
        if is_prime_naive(n) == True:
            answer += 1
    
    return answer

아주 기본적인 방식으로 문자열 -> 문자 -> 조합 -> 정수로 만들어서 정수가 소수인지 판단하는 방법으로 완성했는데 (가능한 수로 계속 나눠서 나눠지면 소수가 아님) 다른 사람들의 풀이를 보니 에라토스네스의 체 방법으로도 가능하다고 한다.

에라토스네스의 체는 2부터 시작해서 2는 소수로 포함, 2의 배수는 모두 소수 아님 -> 3은 소수로 포함, 3의 배수는 모두 소수 아님 -> ... 이렇게 반복하는 방식.
set()을 이용하여 파이서닉하게 코드를 완성할 수 있다.
이외에도 라이브러리 없이 구현하기 등.. 여러가지 해결을 봤다. 문제는 하나인데 방법은 끝도 없네. 역시 코드의 세계는 무궁무진하다..!