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

programmers.co.kr/learn/courses/30/lessons/42839

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

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

완전탐색 문제

 

단순히 조각을 1개부터 len(numbers)개를 사용해서 만들 수 있는 모든 수를 소수인지 아닌지 판별하는 문제.

 

소수 n을 판별하기 위해서는 2부터 sqrt(n)까지 나누었을 때 나머지가 0이 되는 경우가 없으면 된다.

 

이는 아래와 같이 증명된다.

  n 을 합성수라 하자. 그러면  n=ab 로 표현할 때, 1<a,b<n 이다.
  만약  a,b 가 둘 다  n의 제곱근보다 크다면 ( a, b > sqrt(n) )
  ab > n 가 되어 n = ab 와 모순이다. 따라서  a,b 중 적어도 하나는 n의 제곱근보다 크지 않다.

 

<파이썬 풀이>

from itertools import permutations
def solution(numbers):
    answer = set()
    for i in range(len(numbers)):
        candidates = permutations(numbers,i+1)
        for num_arr in candidates:
            num = int(''.join(num_arr))
            if num>1 and num not in answer:
                for k in range(2,int(num**.5)+1):
                    if num%k==0: break
                else: answer.add(num)
    return len(answer)