[ALGOS STUDY] 2023-1-WEEK5 정수론

유클리드 호제법

- 유클리드 호제법의 정의

(https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324)

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.

정수 a, b, q, r (b ≠ 0)에 대해서 a = bq + r이면 G(a, b) = G(b, r)이 성립한다.

 

- 유클리드 호제법으로 최대공약수 구하기

int gcd(int a, int b)
{
    while (b != 0)
    {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

- 유클리드 호제법으로 최소공배수 구하기

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

- 문제 풀이 예시 : 백준 2609 최대공약수와 최소공배수 (https://www.acmicpc.net/problem/2609)

#include <iostream>
using namespace std;

int gcd(int n, int m)
{
	while (m != 0)
	{
		int tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

int lcm(int n, int m)
{
	return n / gcd(n, m) * m;
}

int main()
{
	int a, b;
	cin >> a >> b;
	if (a > b) cout << gcd(a, b) << "\n" << lcm(a, b);
	else cout << gcd(b, a) << "\n" << lcm(b, a);
	return 0;
}

 

에라토스테네스의 체

- 소수를 구하는 알고리즘

• 에라토스테네스의 체
• 오일러의 체
  • 시간복잡도 : O(N)
  • 에라토스테네스의 체의 단점 보완
  • 합성수에 대한 중복 연산을 제거한 알고리즘
  • 2 ~ N까지의 리스트를 생성하고, 리스트의 첫번째 숫자에 대한 배수를 모두 리스트에서 제거하는 알고리즘
• 순다람의 체
  • 시간복잡도 : O(NlogN)
  • 1~N까지의 정수 리스트에 대해서1 ≤ i ≤ j이고, i+j+2*i*j ≤ N인 모든 수를 제거한 후 나머지 숫자에 2를 곱하고 1을 더해서 홀수 소수 리스트를 도출함.
• 앳킨의 체
  • 시간복잡도 : O(N / log log N)
  • 복잡한 작업을 수행한 다음에 소수의 제곱 배수를 제거하는 알고리즘

 

- 에라토스테네스의 체의 정의

(https://terms.naver.com/entry.naver?cid=40942&docId=1179083&categoryId=32204)

2부터 n까지의 숫자 중에서 최초의 소수인 2의 배수를 지우고, 다음 소수인 3의 배수를 지운다. 소수의 배수를 지우는 과정을 소수 p가 p*p ≥ n이 될 때까지 지속한다.

 

- 에라토스테네스의 체 구현 및 시간복잡도

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
}

int main() {
    int n;
    cin >> n;
    sieveOfEratosthenes(n);
    return 0;
}

• 시간복잡도 : O(N log log N)

 

- 에라토스테네세의 체 활용 : 소인수분해

• 자연수를 소인수분해한 결과는 소수들의 곱임을 이용
• 2 ≤ i ≤ n인 i 에서 n을 i로 나눠 n이 i로 나눠지지 않을 때까지 나눔 + i를 증가시켜감.
• 시간복잡도 : O(N log log N

 

- 문제 풀이 예시 : 백준 6588 골드바흐의 추측 (https://www.acmicpc.net/problem/6588)

#include <iostream>
using namespace std;
#define MAX 1000001

int arr[MAX] = { 0, }; // 0이면 소수

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, i, j;
	arr[1] = 1;

	for (int i = 2; i*i< MAX; i++)
	{
		if (arr[i] == 0) for (int j = i * i; j < MAX; j += i) arr[j] = 1;
	}

	while (1)
	{
		cin >> n;
		if (n == 0) break;
		i = 2;
		while (i< MAX)
		{
			j = n - i;
			if (arr[i] == 0 && arr[j] == 0)
			{
				cout << n << " = " << i << " + " << j << "\n";
				break;
			}
			i++;
		}
		if (i == MAX) cout << "Goldbach's conjecture is wrong.\n";
	}
	return 0;
}

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 주차는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다.