[Programmers] level2 - k진수에서 소수 개수 구하기 (Python) : 2022 KAKAO BLIND RECRUITMENT

▶k진수에서 소수 개수 구하기 - 2022 KAKAO BLIND RECRUITMENT (level 2)

▶풀이

주어진 숫자를 k에 맞춰 진수로 바꿔준다.

word라는 string을 하나 만들어서 k로 나눈 나머지를 계속해서 앞에다 넣어주는 방식으로 진수를 만들었다.

그다음에 숫자 '0'을 기준으로 split를 해주어 words에 저장한다.

 

그 숫자들을 하나씩 가지고 와서 소수인지 아닌지 확인하는 코드를 돌려 

소수라면 answer를 1 증가시켜준다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

혹시 소수 구하는 방법이 궁금하다면 위에 나온 위키를 참고해보면 될 것이다.

물론 1부터 n까지 다 비교해보아도 되지만

그렇게 하면 시간 초과 나는 경우가 많아서 에라토스테네스의 체를 사용하면 빠르게 풀 수 있을 것이다.

def solution(n, k):
    answer = 0
    word = ''
    while n:
        word = str(n%k) + word
        n = n//k
        
    words = word.split('0')
    for w in words:
        if w == '':
            continue
        elif int(w) == 1:
            continue
        sosu = True
        for i in range(2, int(int(w) ** 0.5) + 1):
            if int(w)%i==0:
                sosu=False
                break
        if sosu == True:
            answer += 1
            
    return answer

효율성 검사가 따로 없기 때문에

정확성만 통과된다면 바로 100점을 받을 수 있을 것이다.