Algorithm-math.md

---

• 진수, 진법

• 최소공배수, 최대공약수

진수와 진법

---

• N 진법으로 문자열을 변환하기

def stoi(s, n):
    ret = 0
    l = len(s)
    for i in range(l): ret += int(s[i]) * n**(l-i-1)
    return ret

=> 활용

• 거듭제곱 연산 baekjoon1629번

• 조건문 + N진수 변환 방법으로 해결 가능

def pow_custom(a, b):
    ret = 1
    while b:
        if b % 2 == 1: ret *= a
        a = a*a
        b //= 2
    return ret

• 큰 수를 곱하는 것은 Python에서도 느리기 때문에 모듈러 연산자를 중간중간에 쓰자!

최대공약수와 최소공배수

---

• 최대공약수(GCD) : 공약수 중 최댓값

  • 최대공약수가 1이면 서로소

• 최소공배수(LCM) : 공배수 중 최소값

LCM(A, B) = A * B / GCD(A, B)

=> GCD만 잘 구하면 LCM은 O(1)에 구할 수 있다.

• 최대공약수

# 정방향 체크
def gcd(a, b):
    ret = 0
    for i in range(min(a, b)):
        if a % i == 0 and b % i == 0:
            ret = i
    return ret

# 역방향 체크 => 더 빠름
def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

• ✅ 😀유클리드 호제법

  • 위의 두 방식보다 훨씬 빠르다

GCD(A, B) = GCD(B, A % B)

# 속도 => O(log N)
def gcd(a, b):
    return b if a % b == 0 else gcd(b, a%b)

소수와 소인수분해

---

• 여러가지 소수 판별법

# 2부터 N-1까지 체크
def isPrime(N):
    for i in range(2, N):
        if N % i == 0: return False
    return True
# 2부터 sqrt(N)까지 체크 
def isPrime(N):
    i = 2
    while i*i <= N:
        if N % i == 0: return False
    return True

에라토스테네스의 체

def era(N):
    ck, p = [False for _ in range(N+1)], []
    for i in range(2, N+1):
        if ck[i] == True: continue
        p.append(i)
        for j in range(i*i, N+1, i):
            ck[j] = True
    return ck, p