003 소수 찾기

Image generator 사용해서 뽑은 이미지. 숫자 아닌 거 섞여 있음. 요즘 GPT 내가 쓰는 말투에 맞춰 대꾸하는 게 재밌다.

 

문제 출처 : https://youtu.be/m3kCKV8oc1g?si=WTrr9omSekICyslD

 

한 자리 숫자가 적힌 종이 조각이 흩어져 있습니다. 

흩어진 종이조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

Loop 활용 

1. 숫자 조합 

2. 소수가 아닌 수 제거 : 에라토스테네스의 체 사용

3. permutation, map, set 등을 활용하여 손쉽게 확인

 

from itertools import permutations

def solution(numbers):
    prime_set = set()

    # 1. Make all possible number combinations from the given numbers 
    for i in range(len(numbers)):
        # print(list(numbers))
        numbers_permutation = permutations(list(numbers), i + 1)
        # print(list(numbers_permutation))
        # print(list(map("".join, numbers_permutation)))
        # print(list(map(int, map("".join, numbers_permutation))))
        numbers_perm_list = map(int, map("".join, numbers_permutation))
        prime_set |= set(numbers_perm_list)
    # print(prime_set)

    # 2. Check if the number is prime
    prime_set -= set(range(0, 2))
    lim = int(max(prime_set) ** 0.5) + 1
    for i in range(2, lim):
        prime_set -= set(range(i * 2, max(prime_set) + 1, i))
    return len(prime_set)

print(solution("17"))

 

3

 

 

☆ 에라토스테네스의 체 멋진 설명 

https://www.algodale.com/algorithms/sieve-of-eratosthenes/

알고달레

 

 

 

재귀 활용 

나갔다 와서 계속 ..