소수 찾기

문제

문제

 

처음 작성한 코드 // 시간 초과 (코드 없어짐..)

 

코드 리뷰 후

def is_prime(n):
    if n<2: return False
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            return False
    else: return True

def solution(numbers):
    from itertools import permutations
    answer = 0
    result = []
    for i in range(len(numbers)):
        result += set(map(int, map(''.join, permutations(numbers, i+1))))
    for i in set(result):
        if is_prime(i): answer+=1
    return answer

 

깨달은 점

1. 모든 경우의 수를 다 따지는 거라면 permutations가 내가 짠 것보다 빠르다..

2. 소수를 찾을 때에는 최대 약수가 sqrt(n) 이하이므로 거기까지만 체크하면 된다.

 -> 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.