프로그래머스 - 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?

접근

주어진 숫자(최대 7개)로 만들수 있는 모든 숫자를 검사해야 합니다.

1개만 고른 순열, 2개만 고른 순열, 3개만 고른 순열 ... N개만 고른순열(N = len(numbers))을 모두 검사해주면 됩니다.

이후 해당 숫자가 소수인지 아닌지 판단한 후 소수라면 결과에 넣으면 됩니다.

가장 중요한 부분은 소수인지 아닌지 판단하는 부분입니다.

당연히 2부터 해당 숫자까지 순회하면서 나눠지는지 보면 되겠지만, 최대로 올 수 있는 숫자가 9999999(999만9999) 이므로 다른 방법을 생각해내야 합니다.

어렴풋이 에라토스테네스의 체가 생각났고, 2부터 sqrt(해당숫자)까지만 검사해보면 소수인지 아닌지 알 수 있다는 증명이 생각나서 적용했습니다.

구현

가능한 숫자순열을 생성하고 int로 바꾸는 과정이 귀찮아서 파이썬으로 풀었습니다.

소수로 판단되는 숫자는 set에 넣어서 011이나 11처럼 다른 순열이지만 같은 숫자인 경우를 고려했습니다.

접근에선 루트를 이용한다 하였지만 sqrt는 실수를 다루기 때문에 성능,정확도 문제가 있다고 판단하여 그냥 제곱했을때 해당숫자보다 작을때까지 루프를 돌렸습니다.

다음은 코드 전문입니다.

from itertools import permutations

def isPrime(num):

    i = 2
    while((i*i) <= num):
        if num%i == 0:
            return False
        i += 1
    return True



def solution(numbers):
    answer = 0
    num_list = []
    res = set()
    for i in range(len(numbers)):
        num_list.append(numbers[i])



    for i in range(1,len(numbers)+1):
        permute = permutations(num_list,i)
        for p in permute:
            temp = ""
            for n in p:
                temp+=n
            int_temp = int(temp)
            if int_temp <= 1 :
                continue
            if isPrime(int_temp):
                res.add(int_temp)


    answer = len(res)
    return answer