PS101 - 정수론(1)

www.youtube.com/watch?v=XzwXF3rcyR4

배수와 약수

양의 정수 a와 b가 있을 때, a를 b로 나눈 나머지가 0이면 자연수 a는 b의 배수이고 b는 a의 약수이다.

a % b == 0

• 배수와 약수 https://www.acmicpc.net/problem/5086
  • 소스 코드: C++ / Python

최대공약수: 유클리드 알고리즘

유클리드 알고리즘을 사용하면 a와 b의 최대공약수를 구할 수 있다.

/*
유클리드 알고리즘
===============
정수 a,b의 최대공약수를 gcd(a,b)라 한다.
gcd(a,b)=gcd(b,a%b)이다. 따라서 작은 쪽 수가 0이 될 때까지 (a,b)=(b,a%b)를 반복하면 a,b의 최대공약수를 구할 수 있다.
*/

//반복문을 사용한 구현
int gcd(int a, int b) {
	if (a < b) swap(a, b);

	while (b > 0) {
		a = a % b;
		swap(a, b);
	}
	return a;
}

//재귀 호출을 사용한 구현
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

a와 b의 최대공약수를 gcd(a,b)라 할 때 a와 b의 최소공배수는 a*b/gcd(a,b)이다.

• 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609
  • 소스 코드(1, 반복문으로 구현): C++ / Python
  • 소스 코드(2, 재귀 호출로 구현): C++ / Python

약수 찾기

양의 정수 n의 약수를 모두 찾는 가장 간단한 방법은 1부터 n까지 모두 나눠보는 것이다.

정수 n은 약수 두 개의 곱으로 나타낼 수 있고, 이 때 두 약수 중 작은 쪽의 크기는 항상 n의 제곱근보다 작거나 같다. 따라서 1부터 n의 제곱근까지만 확인해도 모든 약수를 찾을 수 있다.

약수가 1과 자신 뿐이면 소수이다.

• 완전수 https://www.acmicpc.net/problem/14563
  • 소스 코드: C++ / Python

bool isprime(int n) {
    if (n == 1) return false;

    for (int i = 2; (i * i) <= n; i++) {
        if (n % i == 0) return false;
    }

    return true;
}

• 소수 찾기 https://www.acmicpc.net/problem/1978
  • 소스 코드: C++ / Python

연습문제

✰

• 배수와 약수 https://www.acmicpc.net/problem/5086
• 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609
• 완전수 https://www.acmicpc.net/problem/14563
• 소수 찾기 https://www.acmicpc.net/problem/1978

✰✰

• 분수 합 https://www.acmicpc.net/problem/1735
• 약수 https://www.acmicpc.net/problem/1037
• 숫자 놀이 https://www.acmicpc.net/problem/12971
• GCD 합 https://www.acmicpc.net/problem/9613
• 소수 https://www.acmicpc.net/problem/2581

✰✰✰

• 링 https://www.acmicpc.net/problem/3036
• 숨바꼭질 6 https://www.acmicpc.net/problem/17087
• 카잉 달력 https://www.acmicpc.net/problem/6064