[프로그래머스] 소수찾기

완전탐색 level2 소수찾기

통과한 코드

from itertools import permutations
def prime(number):
    number = int(number)
    if number == 1:
            return False
    for n in range(2, number//2 + 1):
        if number % n == 0:
            return False
    return True

def solution(numbers):
    numbers = list(numbers)
    s = set()
    
    for n in range(1, len(numbers)+1):
        for l in list(permutations(numbers, n)):
            a = ''.join(l).lstrip('0')
            if a != '' and prime(a):
                s.add(a)

    answer = len(s)
    
    return answer

알게된 부분

기존 prime 함수는 다음과 같았다.

시간 초과는 아닌데 아래와 같이 시간이 많이 걸린 것을 확인했다.

[질문하기]에서 검색해보니 소수를 검색할 때는 전부다 검색할 필요없이 절반만 검사해보면 그 수가 소수인지 아닌지 알 수 있다는 글을 발견했다.
따라서 아래와 같이 소수 찾는 range를 변경하였다.

그 결과 아래와 같이 시간이 단축된 것을 확인할 수 있었다.

공부한 부분

에라토스테네스의 체