programmers k진수에서 소수 개수 구하기

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

프로그래머스

---

level2가 맞나 싶을정도로 구현하기 어려웠던 문제.. 알고리즘은 에라토스테네스의 체 하나 정도 들어가는거 같고...

 

진수변환을 어떻게 하나 고민하다가 보니 다른 블로그가 눈에 들어와서 인용해서 사용했습니다...ㅎㅎ

 

알고리즘적으로 큰 문제는 없으나, 문자열을 0을 기준으로 나누어 주는대에 있어 split()사용은 필수적인거 같다

 

split()은 문자를 괄호안 기준으로 나누어주는데, 위 문제에선 for문을 돌려 '0'을 뽑아내는것 보다 시간적으로 훨씬 수월하고 효과적임을 알수 있음

 

또, 기존에 알고 있던 에라토스테네스의 체 를 이용하여 소수를 찾으려면 엄청난 배열의 길이가 필요하므로, 루트를 이용하여, 소수인지 아닌지 찾는 법이 런타임에러가 안나옴!

 

난 기존에 알고 있던 에라토스테네스의 체 방법으로 소수인지 아닌지 구별하는 배열을 만들었는데, 배열의 길이가 1000만이 되어도 위 배열의 길이를 넘어가 런타임 에러가 떴었음.. 그래서 앞으론 루트를 이용한 소수 구하는 방법을 사용할 생각..

# 루트를 이용한 소수를 구하기
def check(num):
    if num <= 1:
        return False
    MAX = int(num ** (0.5))
    print(MAX)
    for i in range(2, MAX + 1):
        if num % i == 0:
            return False
    return True

# 진수변환
def convert(n, base):
    result = ''
    while n > 0:
        n, mod = n // base, n % base
        result += str(mod)
    return result[::-1]


def solution(n, k):
    answer = 0
    string = convert(n, k)
    num = ""

    # 0을 기준으로 숫자를 나눈 뒤, 숫자들을 하나씩 소수인지 확인
    for num in string.split("0"):
        if not num: continue
        if check(int(num)):
            answer += 1

    return answer