2024/03/01 TIL - Euclidean algorithm(유클리드 호제법), 소수 판별

Euclidean algorithm(유클리드 호제법)

• 두 자연수 또는 정수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 가장 오래되고 효율적인 알고리즘 중 하나다.
• 이 알고리즘은 기원전 300년경 유클리드의 《원론》에서 처음 소개되었으며, 두 숫자의 최대공약수를 찾기 위해 나머지 연산을 반복적으로 사용한다.

유클리드 호제법의 기본원리

• 두 자연수 (A)와 (B)에 대해 ((A > B)) (A)를 (B)로 나눈 나머지를 (R)이라 할 때, (A)와 (B)의 최대공약수는 (B)와 (R)의 최대공약수와 같다.
• 이 과정을 (R)이 0이 될 때까지 반복하면, 마지막으로 나누는 수 (B)가 (A)와 (B)의 최대공약수(GCD)가 된다.

유클리드 호제법의 절차

1. 두 수 (A)와 (B)에서 (A > B)를 만족하도록 정렬한다.

• A > B 전통적인 유클리드 호제법 실제 구현에 있어서 크기 필요없음

2. (A)를 (B)로 나눈 나머지 (R)을 계산한다.

3. 만약 (R)이 0이면, (B)가 최대공약수가 된다.

4. (R)이 0이 아니라면, (A)에 (B)를, (B)에는 (R)을 대입하고 2단계로 돌아가 반복한다..

---

EX) 48과 18의 최대공약수를 구하는 과정

1. (48)을 (18)로 나눈 나머지는 (12).

2. (18)을 (12)로 나눈 나머지는 (6).

3. (12)를 (6)으로 나눈 나머지는 (0).

4. 따라서, 48과 18의 최대공약수는 (6).

유클리드 호제법은 그 효율성 때문에 컴퓨터 알고리즘, 특히 암호학 분야에서 널리 사용된다. 이 알고리즘은 두 수의 크기에 상관없이 매우 빠르게 최대공약수를 찾을 수 있다.

---

최소 공배수 (Least Common Multiple, LCM) 구하는 방법

• 두 수가 있을 때 두 수의 곱을 그들의 최대공약수(Greatest Common Divisor, GCD)로 나눈 값은 그 두 수의 최소공배수(Least Common Multiple, LCM)가 된다.

• 최대공약수(Greatest Common Divisor, GCD), 최소공배수(Least Common Multiple, LCM), 두 수 a, b는 다음과 같은 관계를 가진다.
  

이 수학적 성질은 두 수의 곱이 그들의 최대공약수와 최소공배수를 포함하는 공통 배수라는 점에 기반한다. 최대공약수는 두 수가 공유하는 가장 큰 약수를 의미하며, 최소공배수는 두 수가 공유하는 가장 작은 배수를 의미한다. 따라서, 두 수의 곱은 최대공약수의 배수이자 최소공배수의 배수이므로, 이 두 수의 곱을 최대공약수로 나누면 최소공배수를 얻을 수 있다.

이 관계는 두 수 또는 그 이상의 수에 대한 최소공배수를 구할 때 유용하게 사용된다. 예를 들어, 두 수의 최대공약수를 유클리드 호제법으로 빠르게 계산한 후, 이를 이용해 최소공배수를 구할 수 있다. 이 방법은 특히 컴퓨터 프로그래밍에서 두 수의 최소공배수를 효율적으로 계산할 때 자주 사용된다.

Python에서의 최소공배수, 최대공약수 구하는 방법

	a, b  = origin_a , origin_b

    while b != 0:
        a, b = b, a % b
    gcd = a  # a가 최종적으로 gcd가 된다.
    
    lcm = origin_a * origin_b // gcd  # 최소 공배수는 최대 공약수 // 두 수의 곱

---

소수(Prime Number)

• 오직 1과 자기 자신으로만 정확히 나누어 떨어지는 1보다 큰 자연수
• 정확히 두 개의 양의 약수(1과 자기 자신)만을 가진다.
• EX) 2, 3, 5, 7, 11, 13
• 2는 가장 작은 소수이며, 유일한 짝수 소수
• 암호학, 수론, 알고리즘 등에서 중요하게 다뤄진다.

소수판별

• 1과 그 수 자신을 제외하고, 어떤 정수로도 나누어 떨어지지 않아야 한다.

def is_prime(n):
    """정석적인 소수 판별"""
    if n <= 1:
        return False
    for i in range(2, n):  # 2부터 n-1까지 모든 수로 나누어보기
        if n % i == 0:  # 나누어 떨어지면 소수가 아님
            return False
    return True  # 나누어 떨어지지 않으면 소수

• 위에는 정석적인 소수판별 함수이다.
• 소수는 1과 본인을 제외하고 약수가 없는 경우인데
• 1과 본인을 제외하고 한번이라도 나누어 떨어진다면 소수가 아니다.

def is_prime(n):
    """효율적인 소수 판별"""
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True    

• 정석적인 소수 판별 함수는 큰 소수를 찾으려 할 때 효율적이지 않다.
• 효율적인 소수 판별 로직은 2부터 n의 제곱근까지의 모든 정수에 대해 n을 나누어 보며, 나누어떨어지는지 확인하는 것이다.
• 제곱근 까지 검사하는 이유
  • n이 소수가 아닐 경우, n을 나누어 떨어뜨릴 수 있는 약수 중 적어도 하나는 n의 제곱근 이하다.
  • 따라서, n의 제곱근까지만 검사하면 소수 여부를 효율적으로 판별할 수 있다.

---

에라토스테네스의 체(Sieve of Eratosthenes)

• 소수를 찾는 효율적인 방법 중 하나로, 특정 범위 내에서 모든 소수를 찾기 위해 고안된 알고리즘
• 기원전 3세기 경 그리스의 수학자 에라토스테네스(Eratosthenes)에 의해 고안되었다.
• 기본 아이디어는 범위 내의 모든 수에 대해 소수의 배수를 차례대로 걸러내는 것으로, 상대적으로 적은 연산으로 많은 소수를 빠르게 찾을 수 있다.

작동방식

1. 2부터 N까지의 모든 수를 포함하는 리스트를 만든다. (여기서 N은 우리가 소수를 찾고자 하는 범위의 최대값.)
2. 가장 작은 수인 2부터 시작하여, 그 수의 배수들을 리스트에서 제거한다. 단, 해당 수는 제거하지 않는다. 첫 번째 수 2는 소수이므로 그 배수들을 리스트에서 제거한다.
3. 리스트에 남아 있는 다음 가장 작은 수를 찾고(소수가 아닌 가장 작은 수를 찾는 이유는 이전의 배수에서 다 걸려졌기 때문이다.), 그 수의 배수들을 모두 제거한다. 이 과정을 N의 제곱근까지 도달할 때까지 반복한다. N의 제곱근 이상의 수에서는 이미 그 이하의 소수들의 배수를 통해 걸러졌을 것이기 때문이다.
4. 남은 수들이 바로 2부터 N까지의 소수다.

예시

• 범위가 2부터 10인경우
• 초기리스트 [2,3,4,5,6,7,8,9,10]
• 2의 배수 제거 [2,3,5,6,7,9]
• 3의 배수 제거 [2,3,5,7]
• 5와 7의 경우 자신보다 큰 배수가 리스트에 없으므로, 남은 리스트가 소수의 집합이다.

장점

• 큰 범위 내에서 소수를 찾을 때 매우 효율적.
• 구현이 간단하며, 실행 속도가 빠르다.

단점

• 리스트를 사용하기 때문에 매우 큰 수에 경우 메모리 사용량이 많을 수 있다.
• 소수를 하나만 찾거나 소수 판별만 필요할 경우 다른 방법이 더 효과적일 수 있다.

Python에서의 구현 예시

def sieve_of_eratosthenes(limit):
    prime = [True for _ in range(limit + 1)]
    p = 2
    while (p * p <= limit):
        if (prime[p] == True):
            for i in range(p * p, limit + 1, p):
                prime[i] = False
        p += 1
    primes = []
    for p in range(2, limit + 1):
        if prime[p]:
            primes.append(p)
    return primes

• 불리언 값은 다른 데이터 타입에 비해 메모리 사용량이 적기 때문에, 대규모 데이터를 처리할 때 효율적이다.

집합을 이용한 에라토스테네스의 체 구현

def sieve_of_eratosthenes_with_set(limit):
    # 2부터 limit까지 모든 숫자를 포함하는 집합 생성
    numbers = set(range(2, limit + 1))
    p = 2
    while p * p <= limit:
        # 현재 수 p의 배수들을 집합에서 제거
        if p in numbers:
            numbers -= set(range(p*2, limit + 1, p))
        p += 1
    return sorted(numbers)  # 소수 집합을 정렬하여 반환

# 예시: 30까지의 소수를 찾기
print(sieve_of_eratosthenes_with_set(30))

• 집합은 해시 테이블을 기반으로 하기 때문에, 불리언 배열에 비해 상대적으로 더 많은 메모리를 사용할 수 있다.

---

상식 (Git Branch)

• 현재 Git에선 Master란 브랜치를 default로 쓰고, Github에선 Master대신 Main으로 default를 쓴다.
• 전통적으로, Git에서는 초기화된 저장소의 기본 브랜치 이름으로 master를 사용해왔다.
• 2020년 Black Lives Matter 운동으로 GitHub은 2020년 10월부터 새로 생성된 저장소의 기본 브랜치 이름을 main으로 변경했다.
• 마스터 브랜치를 메인 브랜치로 이름변경 하기 위해서는 git branch -M main 입력하면 된다.
• Git에서 기본 브랜치 이름을 main으로 변경하려면, Git 버전 2.28 이상에서 다음 명령을 사용하여 전역 설정을 변경할 수 있다.

git config --global init.defaultBranch main