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

문제 출처 및 풀이 코드

2022 KAKAO BLIND RECRUITMENT

깃헙 코드

문제 요약

• 1부터 1000000 사이의 숫자를 k 진법으로 변환한다. (k는 3에서 10 사이의 정수)
• k진법으로 변환된 수에서 숫자 0을 기준으로 숫자들을 쪼갠다. (쪼갠 숫자들은 0을 포함하지 않는다)
• 쪼개어 얻어진 숫자들이 소수인지 판별하고 소수의 갯수를 반환한다.

문제 풀이

• 풀이는 문제 요약과 같다.

코드

def solution(n, k):
    
    # k 진법으로 변환된 각 자리수를 저장하는 리스트
    k_base = []
    # n이 0이 될떄까지
    while n > 0:
        # k로 나눈 나머지들을 저장한다.
        # k의 i승으로 나눈 나머지는 k 진법의 i-1 자리에 해당한다는 사실을 기억하자.
        k_base.append(str(n%k))
        n //= k

    # k 진법을 역으로 구하였으므로 이를 역전함
    # 그리고 0을 기준으로 문자열을 쪼개어서 숫자를 구함
    # List comprehension을 통해 공백 문자열을 걸러내고 정수화하는데
    # 아래의 for 문에서 걸러내도 상관 없다.
    nums = [ int(n) for n in (''.join(k_base[::-1])).split('0') if n]

    answer = 0
    # 담겨있는 숫자마다
    for num in nums:
        # 1은 소수가 아니므로 제외
        if (num == 1):
            continue
        # 2 체크
        if (num == 2):
            answer += 1
            continue
        # 값이 3 이상인 경우
        else:  
            # 2 이후의 소수는 모두 홀수 이므로 2씩 더하고, 거듭제곱이 아닌 이상 제곱근까지의 수를 검사하면 소수 판별 가능
            for i in range(3, int(num**0.5)+1, 2):
                if num % i == 0:
                    break
            # 만약 약수가 존재하지 않은 경우
            else:
                answer += 1
    return answer

이 번에 새로 배운 것

• 최초의 풀이는 에라토스테네스의 체를 통해 문제를 푸려고 시도하였다.
• 그런데 런타임 오류가 나서 계산해보니 1000000의 3진법은 1212210202001이다. 따라서 1000000보다 작은 숫자에서 1111111111111라는 숫자가 발생 가능하고, 그럼 에라토스테네스의 체를 구성하기 위해 좀 더 효율이 좋은 5 mod 6 및 1 mod 6의 집합으로 집합을 초기화 할 때 대략 1천억개의 메모리를 요구한다. 따라서 런타임 에러가 발생한다.