[프로그래머스/42839/level2] 소수 찾기 - 에라토스테네스 체 알고리즘 사용하기 & set 장점 활용

문제

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

• 0으로 시작하는 숫자에 대한 처리
• 순열 사용 -> 중복된 값이 있는 리스트 주면, 중복된 순열의 결과가 나올 수 있음
• 소수 판별하는 법 - 에라토스테네스 체 알고리즘 사용하기

내 풀이(알고리즘 적용 전)

from itertools import permutations

def solution(numbers):
    result = 0
    
    #자릿수만큼 순열
    for i in range(1, len(numbers) + 1):

        #i 자리수 순열 중복제거
        p = list(set(list(permutations(numbers, i))))

        for k in p:
            # 0으로 시작하는 것 삭제 = 어차피 그전 조합으로 나왔을 것
            if k[0] == '0':
                continue
            
            num = int(''.join(k))

            # 0, 1 루프 pass
            if num < 2:
                continue
            
            #소수 판별
            for i in range(2, num):
                if num % i == 0:
                    break
            else:
                result += 1
            
    return result

에라토스테네스 체 알고리즘 + set 특징 이용으로 수정 버전!!!!

• 소수 푸는 빠른 알고리즘 : 에라토스테네스의 체 알고리즘 (Python)
  • 가장 작은수 ~ N의 제곱근까지 루프 : 배수를 모두 제거함(합성수니까 제거)
    • 남은 수가 소수임
    • nlogn의 엄청 빠른 시간복잡

from itertools import permutations

def solution(numbers):
    result = set()
    
    #자릿수만큼 순열
    for i in range(1, len(numbers) + 1):
        
        # 1)순열 리스트 요소를 문자열로 map -> 2) 문자열을 정수로 map -> 3) 중복제거 -> 4)합집합
        # 장점: 코드가 한 줄됨, 0으로 시작하는 경우 자동으로 제거됨
        # 합집합
        result |= set(map(int, map(''.join, permutations(numbers, i))))
    
    # 0, 1 제거
    result -= set(range(0, 2))

    #아레토스테네스 알고리즘 - 소수 제거
    #2~ 가장 큰 수의 제곱근 수의 배수들이 존재한다면 제거 -> 남은게 소수임
    for i in range(2, int(max(result) ** 0.5) + 1):
        # i의 배수 차집합 - ix2 부터 시작해서 젤 큰 수까지
        result -= set(range(i * 2, max(result) + 1, i))

    return len(result)