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

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

프로그래머스

import math
def isprime(num): # 소수인지 판별
    if num < 2:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def translate(n,k): # k진수로 변환
    st = ''
    while n > 0:
        st += str(n % k)
        n //= k
    return st[::-1]

def check(n):
    zero=n.split('0') # 0기준으로 나누어 소수인지 비교하기
    cnt=0
    for i in zero:
        if i!='':
            if isprime(int(i)):
                cnt+=1
    return cnt
    
def solution(n, k):
    n=translate(n,k)
    return check(n)

아래코드는 두개가 계속 런타임 에러가 떴었다. 범위가 초과해서 그랬던것 같다.

위의 코드에서는 그 수의 제곱근까지만 판별하였다.

import math
MAX=100000 # 에라토스테네스의 체
prime=[True for i in range(MAX)]
prime[1]=prime[0]=False
for i in range(2,int(math.sqrt(MAX))+1):
    if prime[i]==True:
        j=2
        while(i*j<MAX):
            prime[i*j]=False
            j+=1   
def isprime(num): # 소수 판별
    return prime[num]

def translate(n,k): # k진수로 변환
    st = ''
    while n > 0:
        st += str(n % k)
        n //= k
    return st[::-1]

def check(n): # 0기준으로 나누어 소수인지 판별
    zero=n.split('0')
    cnt=0
    for i in zero:
        if i!='':
            if isprime(int(i)):
                cnt+=1
    return cnt
    
def solution(n, k):
    n=translate(n,k)
    return check(n)