[프로그래머스] 파이썬 _ 소수찾기

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

코딩테스트 연습 - 소수 찾기

 

문제유형 : 순열, 에라토스테네스의 체 

 

문제풀이 : 

• 주어진 문자열을 리스트로 변환후에, permutations라이브러리를 이용해 모든순열은 구한다.
• 다시 문자열로 만들고 숫자로 변환한뒤 (001 -> 1), 집합 자료구조에 넣는다. (중복방지)
• 에라토스테네스의 체를 이용하여 집합에서 가장큰 숫자를 끝으로 해서 가능한 모든 소수를 찾는다.
• 집합을 순회하면서 base배열과 비교해 0이아니면 해당숫자는 소수임을 의미하므로 소수의 총 개수를 찾을 수 있다.

 

정답코드:

from itertools import permutations
def solution(numbers):
    answer = 0
    numbers = list(numbers)
    len_num = len(numbers)
    
    number_list = set()
    
    for i in range(1, len_num+1):
        for case in permutations(numbers, i):
            number = int(''.join(case))
            number_list.add(number)
    
    number_list = list(number_list)
    end = max(number_list)
    
    base = [i for i in range(end+1)] # 인덱스와 숫자를 맞추기위해 0부터 시작 
    base[1]=0 # 1은 0으로 초기화 
    
    for i in range(2, end):
        if base[i] == 0:
            continue
        for j in range(2, end//i+1):  # 얼마까지 곱할수있는가 , end//i 까지
            if base[i*j] == 0:
                continue    
            base[i*j] = 0
    
    for i in number_list:
        # base[i]가 0이면 소수가 아님 
        if base[i] != 0:
            answer += 1
    return answer