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

문제

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

프로그래머스

 

어려운 문제만 풀다보니 힘들어서.. 이번엔 좀 라이트한 문제로

---

 

주요 아이디어

• 소수 구하는 함수 따로 작성
• 주어진 문자열로 만들 수 있는 모든 숫자 조합 생성하기
• 가능한 소수 카운트!

 

---

 

코드 구현 (Python 3)

 

from itertools import permutations

def prime_num(x):
    # 1, 자기자신 외 약수
    # 약수 구하기
    if x < 2:
        return False
    
    elif x == 2:
        return True
    
    else:
        for i in range(2, x):
            if x % i == 0:
                return False

        return True
        

def solution(numbers):
    # 모든 조합
    numbers = [x for x in numbers]
    perm_list = []
    answer = 0
    
    for i in range(1, len(numbers)+1):
        perm = permutations(numbers, i)
        perm = [int(''.join(x)) for x in perm]
        perm_list += perm
    
    perm_list = list(set(perm_list))
    
    for num in perm_list:
        if prime_num(num) == True:
            answer += 1
    
    return answer

 

 

제출 결과

---

 

코드 개선 방안

이번에는 그냥 약수를 찾는 것으로 풀렸지만, 시간 조건이 빡빡한 경우에는 소수 찾기에서도 시간 초과가 걸리는 경우가 있어서 추가로 적어둔다.

 

에라토스테네스의 체

https://ko.wikipedia.org/wiki/%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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

핵심은 n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n) 까지만 검사하게끔 range 범위를 좁혀주는 것이다. 

def check_prime(num):
    if num == 1: return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True