(Python/LV2) k 진수에서 소수 개수 구하기

728x90

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이:

실패 코드

def sosu(k):
    if k < 2:
        return 0
    else:
        for i in range(2, k):
            if k%i == 0:
                return 0
        return 1
def solution(n, k):
    change_n = ""
    while n:            # 숫자를 k진법으로 변환
        change_n = str(n%k) +change_n
        n = (n//k)

    count = 0
    list = map(int,change_n.split('0'))
    for prime_number in list:
        count += sosu(prime_number)
    return count


72.6 / 100

런타임 에리가 난다
이유는 '' 이 들어갔을때

72.6점 코드 런타임 에러가 몇개 난다

def sosu(k):
    if k < 2:
        return 0
    else:
        for i in range(2, k):
            if k%i == 0:
                return 0
        return 1

def solution(n, k):
    change_n = ""
    while n:            # 숫자를 k진법으로 변환
        change_n = str(n%k) +change_n
        n = (n//k)
    count = 0
    lst = change_n.split('0')
    for prime_number in lst:
        if len(prime_number) == 0 :
            continue
        count += sosu(int(prime_number))
    return count


1문제가 시간초과 나옴

88.1 / 100

소수 구하는 방법을 제곱근을 이용하여 바꿔준다.

def sosu(k):

    for i in range(2,int(int(k) ** 0.5)+1): # 소수찾기
        if int(k) % i== 0:
            return 0
    else:
        return 1
        
def solution(n, k):
    change_n = ""
    while n:            # 숫자를 k진법으로 변환
        change_n = str(n%k) +change_n
        n = (n//k)
    count = 0
    lst = change_n.split('0')
    for prime_number in lst:
        if len(prime_number) == 0 :
            continue
        if int(prime_number) < 2:
            continue
        count += sosu(int(prime_number))
    return count

진수 변환하는법은