최소공배수, 최대공약수(유클리드호제법), 소수(에라토스테네스의 체), n진수 만들기

1. 최소공배수, 최대공약수 구하기

파이썬에서 기본 gcd 라이브러리를 제공

from math import gcd

def solution(n, m):
    answer = gcd(n,m)
    return answer

유클리드 호제법

숫자 n, m가 있을 때(단 n>m), n를 m로 나눈 나머지(re)와 m 의 최대 공약수 는 n 와 m 의 최대 공약수 가 같다는 것을 의미한다.

# gcd
def gcd(n, m):
    while m > 0:
        n, m = m, n % m
    return n

최소공배수

from math import gcd

def lcm(a, b):
    return a * b // gcd(a,b)

2. 소수구하기: 에라스토스테네스의 체

배수들을 소수 목록에서 제거하는 방식

n의 제곱근까지만 알아봐도 된다. (나눠지는 수가 있다면 제곱근을 기준으로 쌍을 이루기 때문)

# n까지의 소수갯수 구하기
def solution(n):
    answer = 0
    candidates = [ True for _ in range(0, n+1)]
    # 인덱스 0, 1 은 소수가 아님
    candidates[0] = False
    candidates[1] = False
    for i in range(n+1):
        if candidates[i]:
            answer += 1
            for k in range(i, n+1, i):
                candidates[k] = False
    return answer
    
# n까지 소수 목록 구하기
def primes(n):
    candidates = [ True for _ in range(0, n+1)]
    # 인덱스 0, 1 은 소수가 아님
    candidates[0] = False
    candidates[1] = False
    
    root_n = int(n ** 0.5)
    for i in range(root_n+1):
        if candidates[i]:
            for k in range(2*i, n+1, i):
                candidates[k] = False
    return [i for i in range(2, n+1) if candidates[i] == True ]

3. n진수 만들기

n진수로 변환하는 내용이 기억이 안날 때가 많은데 다음과 같이 변환하는게 제일 간단한 듯 하다.

# 정수 n을 3진법변환 예시
def solution(n):
    answer = ''
    while n > 0:			
        # 3으로 나눈 몫이 다시 n이 되고, 나머지가 3진법의 자릿수가 된다.
        # n 진법으로 나눌 때, n으로 나눠가면서 몫이 0이될때까지 나누며 나머지 값으로 구한다.
        n, re = divmod(n,3)	
        answer += str(re)
    # 이렇게 구한 내용을 거꾸로 해주면 3진법으로 변환된다.
    answer[::-1]
    return answer

n진수 -> 10진수로 만들고 싶다면 int 함수를 사용

# 4진수 232를 10진수로 변환
# int(n진수문자열, n진수)
int('232', 4)