소수 찾기

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

🤔생각해보기

1. 문자열을 한자리씩 판별하여 소수인지 확인해본다. 이 과정에서 소수인지 검사해야하므로 소수 체크 함수를 하나 만들어준다.
2. 소수라면 따로 배열에 담아 놓는다.
3. 한자리씩 검사가 끝났다면, 문자열을 다양한 조합으로 변형해야하므로 permutations 을 사용하여 모든 경우의 수를 만들어준다.
4. set() 자료형을 활용하여 '3번'으로 생긴 경우의 수 중복을 제거한다.
5. 숫자들이 소수인지 체크하고 '2번'을 실행한다.
6. 소수들이 담긴 배열의 길이를 return 한다.

성공

from itertools import permutations
import math


# 소수 검사
def is_prime(n):
    if n in (0, 1):
        return False

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True


def solution(numbers):
    answer = set()

    # 한자리 판별
    for i in numbers:
        if is_prime(int(i)):
            answer.add(int(i))

    # 여러 자리수 판별
    for i in range(2, len(numbers) + 1):
        nums = set(map(lambda x: int(''.join(x)), permutations(numbers, i)))

        for num in nums:
            if is_prime(num):
                answer.add(num)

    return len(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))  # 0, 1, 2 는 소수가 아니므로 제거
  
      # 에라토스테네스의 체
      for i in range(2, int(max(a) ** 0.5) + 1):
          a -= set(range(i * 2, max(a) + 1, i))
      return len(a)

모든 경우의 수를 담아놓은 후, 소수인 값들을 제거하는 방법이다.