프로그래머스 Level2 "소수 찾기"

문제

프로그래머스 소수찾기

풀이

itertools의 permutations(순열)을 이용하여 글자를 조합하는 경우의 수를 찾아내고,
set 자료형을 이용하여 중복을 제거한다.
그 뒤 소수인지 판별하면 되는 문제!

에라토스테네스의 체

소수는 에라토스테네스의 체를 이용하여 구하였다.

0과 1은 소수가 아니니 제외하고 2부터 시작한다.
2를 소수에 추가하고 2의 모든 배수를 지우고 난 후, 
3을 소수에 추가하고 지워지지 않은 3의 모든 배수를 지운다.
4는 이미 지워졌으므로 지나간다.
5는 지워지지 않았으므로 소수이며, 소수에 추가하고 5의 모든 배수를 지운다
.
.
.

이런 식으로 계속 반복을 진행하면 소수만이 남게 된다.
이를 에라토스테네스의 체라고 한다.

위키 백과

Python 코드

from itertools import permutations

def primeCheck(n):
  # 에라토스테네스의 채를 이용한 소수 리스트를 반환하는 함수
  checklist = [False,False] + [True]*(n-1)
  primes=[]

  for i in range(2,n+1):
    if checklist[i]:
      primes.append(i)
      for j in range(i*2, n+1, i):
          checklist[j] = False

  return primes

def solution(numbers):
  # itertools의 순열 메소드를 이용한 경우의 수 저장
  sets = []
  for i in range(1, len(numbers)+1):
    sets += list(permutations(list(numbers), i))

  # 문자열 이어 붙인 뒤 숫자로 자료형을 바꾸고 
  # set을 이용해 다시 한번 중복 제거 ('011'이 숫자형 11로 바뀌면서 생기는 중복 제거)
  numlist = []
  for x in sets:
    temp = ''
    for y in x:
      temp += y
    numlist.append(temp)

  numlist = list(set(list(map(int, numlist))))

  # 소수인지 확인
  primetable = primeCheck(max(numlist))
  answer = 0
  for k in numlist:
    if k in primetable:
      answer += 1

  return answer