[프로그래머스/PYTHON] 소수찾기

안녕하세요

프로그래머스 '소수 찾기' 문제 풀이입니다.

 

문제는 아래의 링크로 확인해주세요!

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

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

 

● 문제 간단 설명

주어진 문자열의 숫자 요소들을 조합하여 가능한 소수들을 모수 찾는 문제입니다.

 

● 문제 해결 방향

저는 일단 주어진 숫자들의 모든 조합을 구하고, 이후 소수를 구하는 방법으로 해당 숫자를 낮은 숫자들로

나누어주면서 소수인지 아닌지를 판별하였습니다.

 

● 문제 해결 코드

from itertools import permutations

def solution(numbers):
    answer = 0
    all = []
    for i in range(1, len(numbers) + 1):
        all += list(set(map(''.join, permutations(numbers, i))))
    
    all = list(set(map(int, all)))
    
    for num in all:
        if num != 0 and num != 1:
            j = 2
            while 1:
                if j == num:
                    answer += 1
                    break
                    
                if num % j == 0:
                    break
                
                j += 1

    return answer

숫자 요소의 조합을 구할 때는 itertool의 permutation을 사용하였습니다.

모든 숫자 조합을 구한 후 각 숫자(n)를 1부터 n-1까지의 수로 나누어 소수를 판별하여 그 수를 카운트했습니다.

 

아무래도 N 아래의 모든 수로 나누다 보니 시간적인 부분이 신경 쓰여서

에라토스테네스의 체로 다시 코드를 짜보았습니다.

from itertools import permutations

def solution(numbers):
    answer = 0
    all = []
    for i in range(1, len(numbers) + 1):
        all += list(set(map(''.join, permutations(numbers, i))))
    
    all = list(set(map(int, all)))

    n = 10 ** len(numbers)
    a = [False, False] + [True] * (n - 1)
    prime = []
    
    for i in range(2, n + 1):
        if a[i]:
            prime.append(i)
            for j in range(2 * i, n + 1, i):
                a[j] = False
                
    for k in all:
        if k in prime:
            answer += 1
    return answer

에라토스테네스의 체는 에라토스테네스가 만들어 낸 소수를 구하는 표이고  그 그림이 체와 같아서

이러한 이름이 붙여졌다고 합니다.

 

● 참고

에라토스테네스 체라는 개념을 가지고 있지 않을 때 어떻게 효과적으로 소수를 구할지에 대한 방법을 생각했었는데

이런 알고리즘은 기본으로 알고 있으면 이후 사용하기 편하겠다는 생각을 했습니다.

 

이상 '소수 찾기' 문제였습니다!