문제

[프로그래머스] 소수 찾기 (LV. 2)

요약

  • 숫자로만 이루어진 문자열이 주어진다. 숫자들의 숫자를 바꿔 만들 수 있는 모든 수 중, 소수의 개수를 반환하라.

분류

  • 완전탐색

풀이

1. 내 풀이

  • 문자열을 리스트로 분리한다. permutations 함수로, 1 ~ n 개의 원소를 사용하여 순열을 만든다. 해당 수가 소수인지 판별한다
  • 소수인지 판별하는 법은, 소수들로 차례로 나누어보면 된다. 하나라도 나누어떨어지는 것이 있다면 소수이다.
  • 결국 소수 판별은, 나머지가 0이냐 아니냐를 판별하는 작업이다. 소수로 나눠주면 더 효율적이지만, 내가 아는 한, 표준 라이브러리에 소수의 목록을 얻을 수 있는 라이브러리는 없다. 따라서 해당 수를 2 ~ 해당 수의 제곱근까지 나누어준다.


from itertools import permutations as per

def is_prime(num):
    if num == 1 :
        return False

    for i in range(2, int(num ** 1/2) + 1):
        if num % i == 0:
            return False

    return True


def solution(numbers):
    answer = 0
    numbers = list(numbers)
    for i in range(1, len(numbers) + 1):
        for num in set(per(numbers, i)):
            if num[0] == "0" : continue

            if is_prime(int("".join(num))):
                answer += 1

    return answer