완전탐색 - 소수 찾기(Prime Number Search)

이번 문제는 주어진 모든 경우의수를 찾고, 여기서 소수를 찾는 문제입니다.

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

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

 

문제를 보면 1~7개 사이의숫자가 주어지고

 

해당 숫자를 가지고 만들어지는 모든 경우의수 중 소수를 찾게됩니다.

 

그렇다면 간단하게 두 파트로 나누면 됩니다.

1. 주어진 1~7개 사이의 숫자로 가능한 모든 경우의 수를 만든다.

2. 경우의수 중 소수인 값을 찾는다.

 

1번의 경우, permutation(순열)조합을 통해서 구할 수가 있습니다.

(중,고등학교때 배운 nPm 입니다)

 

개수가 1~N개까지의 모든 Permutation을 합치면 모든 경우의수를 확인할 수 있습니다.

 

소수같은 경우는 Prime Number 찾기 포스팅에서 사용한 방법을 사용했습니다.

teus-kiwiee.tistory.com/61

Prime Number 여부 확인(단순탐색)

해당 문제의 Python 해답 Code입니다 :)

 

import itertools
import math

def isprime(n):
	#Number의 중간 지점까지만 소수 여부 확인    
    for i in range(2,math.ceil(n/2)+1):
    	#n을 나눠서 0이되는 값이 있을경우 소수가 아니므로
        #0을 반환
        if divmod(n,i)[1] == 0:
            return 0
    #n<=1인 경우 위 로직으로 판단이 불가하므로 예외처리
    if n<=1:
        return 0
    #소수인 경우에는 1을 반환
    return 1


#ex. numbers = "19756"
def solution(numbers):    
    #1~N개의 Permutation결과를 저장할 임시 List
    temp =[]
    #반복문을 통해서 i값에 따른 permutation 조합을 모두 구합니다.
    for i in range(1,len(numbers)+1):
        temp = temp + list((itertools.permutations(numbers, i)))
    #구해진 값들을 String -> Int 로 convert해 줍니다.
    for i in range(len(temp)):
        temp[i] = int("".join(temp[i]))
    #중복값 제거
    temp = list(set(temp))
    #isprime함수를 활용해서 소수인경우 1, 아닌경우 0을 반환해
    #temp에 소수가 몇개있는지 구합니다.
    answer = 0    
    for i in temp:
        answer = answer + isprime(i)            
    return answer