Easy is Perfect

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

  • melonicedlatte
  • Aug 18, 2020


1. 문제

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

2. 풀이

2.1. 에라토스테네스의 체와 permutation을 이용한 풀이

  • 먼저 에라토스테네스의 체를 이용하여 최대 숫자로 가능한 9999999 까지 소수를 저장합니다.
  • 최대 7개의 숫자를 permutation을 각 자리수마다 수행하여 모든 나올 수 있는 수를 생성합니다. 이 숫자를 소수인지 아닌지 확인하고 set에 추가합니다.
  • 최종적으로 set의 원소의 개수를 확인하여 정답으로 출력합니다.
from itertools import permutations

def solution(numbers):
    ## make sosu table
    MAX_NUM = 9999999
    is_sosu = [1] * (MAX_NUM + 1)
    is_sosu[0] = is_sosu[1] = 0
    for i in range(2, MAX_NUM):
        if is_sosu[i] == 0:
            continue
        t = 2
        while i * t <= MAX_NUM:
            is_sosu[i * t] = 0
            t += 1

    ## make number and check
    answer = []
    sub_numbers = list(numbers)
    for i in range(1, len(sub_numbers) + 1):
        permute = permutations(sub_numbers, i)
        for x in permute:
            this_number = int(''.join(x))
            if is_sosu[this_number] == 1:
                answer.append(this_number)

    return len(set(answer))

2.2. 에라토스테네스의 체와 permutation을 이용한 풀이의 숏코딩

  • 프로그래머스에서의 숏코딩으로 전체적인 풀이는 위와 같습니다.
  • 차이점으로는 set을 이용하여 permutation 결과를 넣고, 해당 결과에서 가장 큰 숫자를 기준으로 소수만 남기고 모든 숫자를 제거하는 방식입니다.
    • 숫자를 제거할 때, range()를 이용하여 제거하여 코드를 크게 줄였습니다.
from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

2.3. 각 숫자마다 소수인지 아닌지를 루트를 이용하여 판별한 방법

  • 역시 프로그래머스에 존재하는 소스코드로 모든 경우의 수를 permutation을 이용하여 구한 후에, 각각 숫자마다 소수인지 아닌지를 확인하는 방법입니다.
import itertools

def is_prime(n):
    prime_number = None
    for i in range(2, n+1):
        if n % i == 0:
            prime_number = i
            break

    return True if n == prime_number else False

def change(value):
    return int(''.join(value))

def solution(numbers):
    answer = 0
    ns = [x for x in numbers]
    result = []

    for i in range(1, len(ns)+1):
        result += list(map(change, itertools.permutations(ns, i)))

    result = list(set(result))
    for i in result:
        if is_prime(i):
            answer += 1
    return answer



Search