[python 알고리즘 팁] 소수판별, 진수 변환

소수 판별

64까지의 약수를 판별하자면 1 x 64, 2 x 32x 4 x 16, 8 x 8로 1, 2, 4, 8, 16, 32, 64의 약수를 갖는걸 알 수 있다

자기 자식의 제곱근까지의 수를 살펴보면 전체 약수를 구할 수 있다. 이렇게 소수를 찾는 방법을 에스테라토스 체라 한다.

 

num(num > 0)이 주어졌을 때 소수인지 아닌지 판별하려면

1. 1이면 소수가 될 수 없다
2. 2이면 소수다
3. 짝수면 2로 나눠지므로 소수가 아니다
4. 그 외 수는 홀수만 살펴보면서 num과 나누었을 때 나머지가 0인 수가 있다면 num은 소수가 아니다

위와 같은 조건들로 코드를 짜면 아래와 같다

import math

# 소수 판별 함수
def check(num):
	# 2이면 소수
    if num == 2:
        return True
    # 1이거나 짝수이면 소수x
    if num == 1 or num % 2 == 0:
        return False
    
    # 그 외 num**0.5보다 작은 숫자들에 대해 하나씩 대조
    # sqrt대신 num**0.5도 가능
    for i in range(3, int(math.sqrt(num))+1, 2):
        # 나누어진다면 소수가 아님
        if num % i == 0:
            return False
    
    return True

 

진법 변환

64의 3진법을 구한다면 64를 계속 나누면서 나오는 나머지를 전부 구해 순서를 뒤집어주면 3진법으로 변환할 수 있다

이 코드에서 알아야 하는 것은 2가지이다

1. divmod(n, b) : n을 b로 나눴을 때 몫과 나머지를 return 한다
2. 재귀 : 자기 자신을 호출하는 함수, 반드시 종료조건 필요 (무한호출 할 수 있음)

# 역순의 나머지 결과가 나옴
def convert(num, base):
	q, r = divmod(num, base)
    # q가 0이 아니면
    if q:
    	# 자기 자신을 호출하는 값에 + 나머지 붙여줌
    	return convert(q, base) + str(r)
       
    else:
    	return str(r)

 

해당 코드들은 [프로그래머스] k진수에서 소수 개수 구하기를 짜면서 필요한 알고리즘입니다.