프로그래머스 소수 찾기 파이썬

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

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

 

크게 어려운 문제는 아니였던듯 한데,, 내가 푼 방법이 효율적이라고는 말하지 못하겠다.

 

내 풀이는 아래와 같다.

 

1. 숫자의 길이만큼 루프를 돌린다.

 

2. 예를들어 1234 면 1자리로 나올수 있는 조합부터 4자리로 나올수 있는 모든 조합을 itertools 의 permutations 를 통해서 구한다.

 

3. 가능한 모든 조합을 순회하면서 소수여부를 판단하기 위해 3 부터 조합한 숫자까지 루프를 돌린다

 

4. 이때 조합한 숫자가 2라면 무조건 소수이니 소수값에 저장하고 3부터 조합한 숫자까지 루프를 돌리는데 짝수면 무조건 소수가 아니기 때문에 홀수로만 나눈다.

 

5. 조합된 수와 홀수를 나눴을때 나눠떨어지면 소수가 아니므로 바로 소수판단 루프를 종료한다.

 

6. 소수로 저장된 list 의 중복을 제거하기 위해 set 에 저장한다.

 

7. 중복이 저장된 소수값들의 길이를 출력한다.

 

 

import itertools


def solution(numbers):
    temp = []
    for i in range(1, len(numbers) + 1):
        nPr = itertools.permutations(numbers, i)
        for j in nPr:
            num = int(''.join(j))

            if num == 2:
                temp.append(2)
            elif not (num == 0 or num == 1):
                is_prime = True
                if num % 2 == 0:
                    is_prime = False
                else:
                    for k in range(3, num, 2):
                        if num % k == 0:
                            is_prime = False
                            break

                if is_prime:
                    temp.append(num)
    return len(set(temp))