[프로그래머스/python/Lv2] k진수에서 소수 개수 구하기

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기

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

프로그래머스

 

코드

import math

def decimalToK(num, k): # k진수로 변환
    kNum = ""
    while num > 0:
        kNum = str(num%k) + kNum
        num = num//k
    return kNum
        
def isPrimeNumber(num):
    if num < 2: # 2 이하의 수는 소수가 아님
        return False
    mid = int(math.sqrt(num))
    for i in range(2, mid+1):
        if num%i == 0: # 약수가 1과 자기자신이 아니라면 소수 아님
            return False
    return True
    
def solution(n, k):
    answer = 0
    kNum = decimalToK(n, k).split("0")
    
    for i in kNum:
        if i != '' and isPrimeNumber(int(i)):
            answer+=1
    return answer

풀이

input을 k진수로 변경 후, 0으로 파싱해준다

파싱된 값을 list에 넣어준 후, list를 순회하면서 ""가 아닐때 and 소수일때 answer+=1해준다

 

---

K진수로 변환

def decimalToK(num, k): # k진수로 변환
    kNum = ""
    while num > 0:
        kNum = str(num%k) + kNum
        num = num//k
    return kNum

num를 k로 나누어주고, 나머지를 kNum문자열의 가장 앞에 추가해준다

num이 0보다 클때만 반복 실행

 

소수판별

소수: 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 

소수판별법: 주어진 수 n을 2부터 n-1까지의 수로 나누어보고, 나누어 떨어진다면 소수가 아님. 나누어 떨어지는 수가 없다면 소수

def isPrimeNumber(num):
    if num < 2: # 2 이하의 수는 소수가 아님
        return False
    mid = int(math.sqrt(num))
    for i in range(2, mid+1):
        if num%i == 0: # 약수가 1과 자기자신이 아니라면 소수 아님
            return False
    return True

 

✅ 2이하의 수는 소수가 아님

✅ 2 ~ int(sqrt(num))+1까지의 범위만 check해준다 (약수의 특성을 활용해 연산횟수를 반으로 줄일 수 있다)

 

약수의 특성

n의 약수들을 일렬로 나열했을 때, 그 중 가운데 수를 중심으로 약수가 대칭된다

예) 16의 약수: 1, 2, 4, 8, 16 -> 4를 기준으로 1, 16과 2, 8이 대칭됨을 알 수 있다

 

따라서, 중간값까지만 약수가 있는지 check해주면 된다