99클럽 코테 스터디 10일차 TIL + 완전탐색: 소수 찾기

문제

링크텍스트

풀이

• notion에서 다른 분들이 푸신 코드를 참조했습니다.
• 소수찾기
  • 풀이과정을 통해 해법을 이해할 수 있었습니다.
  • ‘에라토스테네스의 체’ 배워야 할 것이 많습니다.
• [소수 찾기](https://school.programmers.co.kr/learn/courses/30/lessons/42839)
  • permutation 함수를 안쓰고 찾아가는 방법이 일품입니다.
• 소수찾기
  • 소수찾기에서 cache를 사용하여 최적화하는 법을 배웁니다.
  • 앞으로도 dictionary를 활용하여 자주 쓰게 될 듯 합니다.
• 이렇게 참조만 하다 언제 실력을 쌓을까 걱정입니다.

결과

def f_t(id_t):
    if id_t == 0:
        n, r = "17", 	3
    if id_t == 1:
        n, r = "011", 	2        
    return n, r
    
def solution(numbers):
    prime_cache = {}
    def is_prime(x):
        if x in prime_cache:
            return prime_cache[x]
        if x < 2:
            prime_cache[x] = False
            return False
        for k in range(2, int((x+1)**0.5) + 1):
            if x % k == 0:
                prime_cache[x] = False
                return False
        prime_cache[x] = True
        return True
    def f_s(id_n, i, ns_i):
        id_n[i] = True
        ns_i += numbers[i]
        n_i = int(ns_i)
        is_prime(n_i)
        for j in range(len(numbers)):
            if id_n.get(j) is None:
                f_s(id_n.copy(), j, ns_i)
    for i in range(len(numbers)):
        id_n = {}
        if numbers[i] != "0":
            f_s(id_n, i, "")
    return sum([i == True for i in prime_cache.values()])
    
for i in range(2):
    print(f'test case {i}')
    n, r = f_t(i)
    a = solution(n)
    print(a)
    print(r)