[프로그래머스] 소수 찾기 - 에라토스테네스의 채, 재귀

아이디어는 어렵지 않았지만, 구현하기 꽤 까다로웠다.

소수를 일일이 판별할 생각은 했지만 찾다 보니 에라토스테네스의 채라는 개념을 보고 아이디어를 얻어 풀었다.

해당 포스트는 아래 첨부한다. 

 

일단 직관적으로 풀었지만, 애초에 2 미만은 제거한다던지 하면 한번 필터하는 작업을 없앨 수 있을 것 같다.

그리고 순열을 구하는 것에 머리가 아팠지만 permutation 라는 걸 쓰면 순열도 쉽게 만들 수 있다더라~~

 

"""
여러개의 수가 소수인지 아닌지 -> 에라토스테네스의 체 
이 수가 소수인지 아닌지 -> 제곱근 까지 나누기

소수 중엔 2빼곤 짝수가 없다.

numbers 의 가능한 모든 조합을 만듬 -> 짝수 제외
가장 큰 수의 에라토스테네스 체를 통해 소수들 구함

교집합

"""
import math
def allCombi(numbers):
    elements = set()
    if len(numbers) == 1:
        return [numbers]
    
    for i in range(len(numbers)):
        current = numbers[i]
        remain = numbers[:i] + numbers[i+1:] # cuurent 빼고 만든 조합
        elements.add(current)
        for p in allCombi(remain):
            elements.add(current+p)
            
    return elements

def sosu(num):
    array = [True for _ in range(num+1)]
    for i in range(2, int(math.sqrt(num))):
        if array[i]:
            j = 2
            while i * j <= num:
                array[i*j] = False
                j += 1
                
    true_indices = [index for index, value in enumerate(array) if value]
    return true_indices

def solution(numbers):
    elements = allCombi(numbers)
    elements_int = [x for x in map(int, elements) if x >= 2]
    max_ele = max(elements_int)
    sosu_li = sosu(max_ele)

    
    intersection = list(set(elements_int) & set(sosu_li))
    answer = len(intersection)
    return answer

 

 

https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%86%8C%EC%88%98%EC%9D%98-%ED%8C%90%EB%B3%84-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[알고리즘] 소수의 판별 - 에라토스테네스의 체

 

https://velog.io/@dramatic/Python-permutation-combination-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

[Python] permutation, combination 순열과 조합