[Programmers] 완전탐색 : 소수 찾기 (Python)

1일 1문제 22일차!

오늘의 문제는 프로그래머스의 완전탐색 소수찾기입니다!

코딩테스트 연습 - 소수 찾기 | 프로그래머스

itertools의 permutation함수와 이전에 풀었던 에라토스테네스의 체 문제를 활용하여 풀어보았습니다.

from itertools import permutations

def getPrimaryNum_Eratos(N): 
    nums = [True] * (N + 1) 
    for i in range(2, len(nums) // 2 + 1): 
        if nums[i] == True: 
            for j in range(i+i, N, i): 
                nums[j] = False 
    return [i for i in range(2, N) if nums[i] == True]



def solution(numbers):
    answer = 0
    
    num_list = list(numbers)
#     print(num_list)
    
    new_comb_list = []
    
    for i in range(1, len(num_list)+1):
        comb_list = list(permutations(numbers, i))
        
        for j in range(len(comb_list)):
#             print(comb_list[j])
            new_comb_list.append(int(''.join(comb_list[j])))
    
    new_comb_list = list(set(new_comb_list))
    
#     print(new_comb_list)
    
    max_num = max(new_comb_list)
    
    sosu_list = getPrimaryNum_Eratos(max_num+1)
    
#     print(sosu_list)
    
    for i in range(len(new_comb_list)):
        if new_comb_list[i] in sosu_list:
            answer = answer + 1

    return answer

permutations을 써야할부분에 combinations를 적어서 고민이 조금 되었지만 그래도 통과!

 

SOMJANG/CODINGTEST_PRACTICE