2진수, 3진수, k진수 변환하는 법 | 파이썬 k진수 변환 | 소수찾기 | 프로그래머스 k진수에서 소수찾기 파이썬

k진수 찾기랑 소수 찾기는 코테에서 꽤나 빈출 유형으로 나오는데 두 가지가 결합된 문제가 있어 정리해본다.  기억해두고 더 이상 헷갈리지 말자. 

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

프로그래머스

k진수 

 k진법이란 0부터 k개의 숫자를 사용해서 수를 표현하는 방법으로, 2진법은 0과 1의 2가지 숫자로 수를 표현한다. 3진법은 0,1,2의 3가지 숫자로 수를 표현한다.  즉, 0부터 k-1까지의 숫자로 수를 표현하는 것을 말한다. 

구하는 방법은 그림과 같다. k진수로 수를 나타내고 싶을 때, k로 몫이 k보다 작아질때까지 나눠준다. 그 후, 몫과 지금까지 나눈 나머지를 쭉 써주면 된다. 

파이썬으로는 다음과 같이 구현할 수 있다. 나머지를 쭉 더해주고 몫을 새로운 n으로 업데이트해준다. 

number =''
while n :
    b = n% k #나머지  
    number = str(b)+number #join으로 하면 나중에 뒤집어줘야함
    n = n // k  #몫

 

소수 찾기 

소수는 1과 자기 자신만을 약수로 가지는 수이다. 즉, 1과 자기자신 외에는 절대 나누어 떨어지지 않는 수를 의미한다. 

만약 n을 1~n 사이의 어떤 숫자로 나누었을 때 0으로 나누어 떨어지는 숫자가 있다면 소수가 아니게 되는 것이다.  

하지만 2부터 n-1까지의 숫자로 나누어 떨어지는지 전부 확인할 경우 굉장히 많은 시간이 소요된다. 

10정도야 2부터 9까지 모두 나눠봐도 탐색하는데에 많은 시간이 소요되지 않지만 238597129576106같은 큰 숫자는 모두 탐색하기가 어렵다. 

n의 모든 약수는 n/2보다 작다는 성질을 가진다. 따라서 굳이 n-1까지 전부 탐색하지 않고 2/n까지만 탐색해도 된다. 하지만 이 방법보다 더 크게 시간 복잡도를 줄일 수 있는 방법이 있다. 

바로 제곱근보다 작은 수들 중에 약수가 없다면, 제곱근보다 큰 수들은 n의 약수가 아니다라는 성질을 이용하는 것이다. 

def isPrime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False  
    return True

 

이렇게 하면 해당 숫자가 소수인지 아닌지 판별할 수 있다.

 

k진수에서 소수찾기 

이를 활용하여 문제를 풀 수 있다.

#n을 k진수로 변환하였을 떄, 변환된 수 안에 조건에 맞는 소수가 몇개 있는지 return 
def solution(n, k):
    ##우선 k진수로 변환 
    number =""
    while n :
        number = str(n% k)+number #join으로 하면 나중에 뒤집어줘야함
        n = n // k  #몫
    number=number.split("0")  #0기준으로 나누기 
    print(number)
    ##조건에 맞는 소수 찾기: 중복되는 소수도 따로 count
    cnt = 0 
    for i in number:
        if len(i)==0:  
            continue
        if int(i)<2:
            continue
        prime=True
        for j in range(2, int(int(i)**0.5 + 1)):
            if int(i) % j ==0:
                prime=False
                break
        if prime:
            cnt+=1
    return cnt