# Algorithm-math.md

***

* 진수, 진법
* 최소공배수, 최대공약수

## 진수와 진법

***

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

```python
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번](https://www.acmicpc.net/problem/1629)
* 조건문 + N진수 변환 방법으로 해결 가능 ![doublemulimage](https://github.com/WoungSub-Byun/TIL/blob/main/Programming/Image/doublemulimage.png)

```python
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)에 구할 수 있다.**

* 최대공약수

```python
# 정방향 체크
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)**

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

## 소수와 소인수분해

***

* 여러가지 소수 판별법

```python
# 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
```

### **에라토스테네스의 체**

> <img src="https://wikidocs.net/images/page/21638/DC-1707V1.png" alt="eratostenes" data-size="original">

```python
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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://woungsub1234.gitbook.io/woungsub-devlog/programming/algorithm/general/algorithm-math.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.