python 코딩테스트 - 소수 찾기

출처 : 프로그래머스

처음 든 생각

- 나올 수 있는 모든 수를 구해야겠다 -> permutations 라이브러리 사용

- 소수인지 아닌지 확인하는 함수는 따로 만들어줘야겠다

- string, number 자료형 구분 잘할 것

 

나의 답

from itertools import permutations
import math

def solution(numbers):
    
    arr =[]
    
    for i in range(1,len(numbers)+1):
        arr.append(list(permutations(numbers,i)))
        
    def checkPrime(num):
        count = 0
        if num <2:
            return False
        for i in range(1, math.floor(num **(1/2))+1):
            if num % i ==0:
                count+=1
            if count >1:
                break
        return True if count <2 else False
        
    numArr = []
    
    for i in arr:
        for j in i:
            num = int("".join(j))
            if checkPrime(num):
                numArr.append(num)
    answer = len(set(numArr))
    
    return answer

모든 경우의 순열을 담을 리스트를 하나 선언해준다.

 

그 다음 소수인지 아닌지 검사하는 함수는 제곱근까지만 약수를 구하여 약수가 2개라면 소수가 아니고 2 미만이라면 소수라고 판단한다.

약수는 무조건 짝으로 존재하므로 제곱근보다 작은 쪽에서 1 이외에 다른 약수가 존재하면 최소 3개 이상이라는 것이기에 소수가 될 수 없다. 완전제곱수일 때도 저 범위에서는 2개로 개수가 측정되기 때문에 식별이 가능하다. 

 

소수를 담을 큰 리스트인 numArr을 선언한 후 모든 경우에 대하여 join을 하여 정수 자료형으로 변환한 다음 소수인지 아닌지 구별하여 리스트에 넣어준다. 겹치는 원소를 제거해주기 위해 set으로 자료형을 바꾼 다음 개수를 세주면 된다.

 

 

가능한 모든 경우를 조사하여 여부를 확인한 다음 개수를 세는 문제였다.

순서대로만 잘 따라가면 풀 수 있었던 문제라 그렇게 어렵지는 않았다.

다만 소수 판별 함수에서의 범위는 유의해서 설정해줘야했다. 처음에 +1 안해줘서 제곱수를 판별하지 못했었다.