[12, 13일차] 07 정수론

함께 푼 문제

[백준 / 정수론] 1978 : 소수 찾기 (python)

소수 구하기

[백준 / 정수론] 11689 : GCD(n, k) = 1 (python)

오일러 피

[백준 / 정수론] 2609 : 최대공약수와 최소공배수 (python)

유클리드 호제법

[백준 / 정수론] 14565 : 역원(Inverse) 구하기 (python)

확장 유클리드 호제법

 

소수 구하기

에라토스테네스의 체

1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.
2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 리스트의 끝까지 2를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다.

A = [i for i in range(1001)]
A[1] = 0

for i in range(2, int(math.sqrt(len(A)) + 1)): # MAX의 제곱근까지만 검사한다.
    if A[i] == 0:
        continue
    for j in range(i + i, len(A), i): # 배수 지우기
        A[j] = 0

• 에라토스테네스의 체를 파이썬으로 구현한 것이다.
• 리스트 A에 소수가 아닌 것은 0으로 저장되고, 소수인 것은 그 수를 저장한다.

 

오일러 피

서로소인 자연수 개수 구하기

 

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다(i는 K의 배수).
3. 리스트의 끝까지 2를 반복하여 오일러 피 함수를 완성한다.

 

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

 

MOD 연산으로 구현

최대 공약수를 구하는 연산은 일반적으로 GCD로 정의한다.

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
3. 단계 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

확장 유클리드 호제법

방정식의 해를 구하는 알고리즘

 

ax + by = gcd(a,b) 일 때, x와 y를 구한다.