42839 소수 찾기

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

 

# 나의 코드 -> 개별 후보에 대해 그 제곱근까지만 약수 여부 검증

- 몫과 나누는 수 둘중 하나는 N제곱근 이하라는 것에 착안.

from itertools import permutations

def solution(numbers):
    
    parts = list(numbers)
    
    candids = []
    for i in range(1, len(parts)+1):
        candids.extend(list(map(lambda x: int(''.join(x)), list(permutations(parts, i)))))
    
    candids = set(candids) - set([0, 1])
    
    n = 0
    for c in candids:
        for i in range(2, int(c**(1/2))+1):
            if c % i == 0:
                break
        else:
            n += 1
            
    return n

 

 

# 다른 사람의 코드 참조해서 수정 (에라토스테네스의 체)

- 소수 판별 범위를 미리 정해두고 배수들을 지워나가는 방식

- 이 경우에는 배열 max값의 N제곱근까지만 보면 됨.

from itertools import permutations

def solution(numbers):
    
    candids = set()
    for i in range(1, len(numbers)+1):
        candids |= set(map(lambda x:int(''.join(x)), permutations(list(numbers), i)))
    
    candids -= set(range(0, 2))
    
    for i in range(2, int(max(candids)**(1/2))+1):
        candids -= set(range(i*2, max(candids)+1, i))
            
    return len(candids)

 

 

 

[개선할 점]

- 대량의 소수를 한 번에 판별할 경우에는 에라토스테네스 체를 사용하면 좋다.

- list에서 set으로 이후에 변환하지 않고, candids를 set으로 만들고 permutations들도 set으로 만들어서 매번 합치면 된다. 집합의 복합 대입 연산자:

* 합집합 -> |=

* 차집합 -> -=

 

- map 결과를 set 또는 list로 wrap할거라면 permutations에서 미리 list로 감싸주지 않아도 된다.

- map에 함수 argument 줄때 map("".join, ~) 이런 식도 가능하다.

- range 범위 시작과 끝에 1을 더하는 것 말고, 실제 사용되는 i에서 i+1로 바꿔줌으로서 range(len(n))으로 쓸 수도 있다.