[Python] 소수 찾기

[코딩테스트 고득점 KIT - 완전탐색]

 

 

모든 경우의 수를 탐색하기 위해 순열을 사용하였다.

 

"011" 와 "11"은 같은 수 이기 때문에

중복 제거를 위해 answer을 set()로 만들어 주었다.

 

약수는 곱의 형태로 반복되기 때문에 제곱근+1 까지만 반복문을 실행한다.

ex) 24의 약수 = 1, 2, 3, 4, 6, 8, 12, 24  →1*24, 2*12, 3*8, 4*6,  따라서 24는 2로 나눠지면서 12로도 나눠지는 수 

 

나누어진다면, 1과 자기 자신만이 약수로 갖는 소수가 아닌 합성수이다.

합성수가 아닌 수는 소수.

 

소수를 담은 리스트의 길이를 반환하면 끝.

 

from itertools import permutations
import math
def solution(numbers):
	# 중복 제거
    answer = set()
    
    for i in range(len(numbers)):
    	# 순열을 통한 경우의 수 실행
        for number in list(permutations(numbers,i+1)):
        	# 문자열 -> 정수
            target = int(''.join(number))
            
            # 2와 3도 소수
            if target == 2 or target == 3:
                answer.add(target)
                continue
            
            # 약수는 곱의 형태로 반복되기 때문에 제곱근+1 까지
            for j in range(2, int(math.sqrt(target)+1)):
            	# 합성수
                if target % j == 0:
                    break
               	# 소수
                elif j == int(math.sqrt(target)):
                    answer.add(target)
    return len(answer)