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

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=python3 

프로그래머스

 

 

 

 

 

🐾 20221021

 

 

 

 

 

 

 

1. k진수로 변환

2. 소수 찾아 개수 구하기

 

 

 

코드 : 

def solution(n, k):
    word = ""
    
    # k 진수로 변환 
    while n :
        word = str(n%k) + word
        n = n//k
    
    word = word.split('0')
    cnt = 0
    for w in word :
        # 빈공간이라면
        if len(w) == 0 : continue 
        # 0 또는 1이라면 
        if int(w) < 2 : continue 
        
        # 소수 찾기 
        sosu = True 
        for i in range(2,int(int(w)**0.5)+1 ) :
            if int(w) % i==0 :
                sosu = False 
                break
        if sosu : cnt+=1 
    
    return cnt

 

 

 

 

 

 

사실 간단한데 너무 어렵게 생각했다. 

진수로 변환하는 법, 소수 판별하는 법은 외우자!!!

 

 

 

 

 

---

 

 

복습하면서 다시 풀어봤는데 

다른건 다 맞았는데 1번에서 시간초과가 났다. 

이유는 소수를 판별할 때 끝까지 다 확인했기 때문이다. 

소수를 판별할 때 제곱근까지만 확인하면 된다!!

 

 

for i in range(2,int(r**0.5)+1) : 
     if r%i ==0 :

 

 

제곱근은 r**0.5를 하면 구할 수 있다.

 

 

 

 

복습하면서 만든 코드 : 

def solution(n, k):
    cnt = 0
    res = ''
    
    # k진수로 만들기 
    while n :
        res+= str((n%k))
        n = n//k
    res = res[::-1]
    
    # 0을 기준으로 split 
    res=res.split('0')
    
    # 소수 판별 
    for r in res :
        if not r : continue 
        isTrue = 1
        r = int(r)
        if r <= 1 : continue 
        # 제곱근까지만 확인하면 된다!!
        # 전부 확인하면 시간초과 
        for i in range(2,int(r**0.5)+1) : 
            if r%i ==0 : 
                isTrue = 0
                break 
        if isTrue : cnt +=1 
        
    
    return cnt

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://velog.io/@hope1213/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-k%EC%A7%84%EC%88%98%EC%97%90%EC%84%9C-%EC%86%8C%EC%88%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[프로그래머스] k진수에서 소수 개수 구하기 (파이썬)

https://jm-park.github.io/algorithm/2018/08/06/Prime-Number(%EC%86%8C%EC%88%98)-%ED%8C%90%EB%B3%84%EB%B2%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.html 

JM's IT Blog