두 숫자의 공약수는 두 숫자의 약수입니다.
예를 들어, 12의 제수는 1, 2, 3, 4, 6, 12입니다. 18의 제수는 1, 2, 3, 6, 9, 18입니다. 따라서 12와 18의 공약수는 1, 2입니다. , 3, 6. 이들 중 가장 큰 것은 아마도 12와 18이라고 불리는 것입니다. 두 정수 a와 b의 최대 공약수에 대한 일반적인 수학적 표기법은 (a, b)로 표시됩니다. 따라서 (12, 18) =6.
최대공약수는 여러 가지 이유로 중요합니다. 예를 들어 두 숫자, 즉 이 숫자의 배수인 가장 작은 양의 정수를 계산하는 데 사용할 수 있습니다. 숫자와 b의 최소 공배수는 a*b*(a, b)
로 계산할 수 있습니다.예를 들어, 12와 18의 최소 공배수는 12*18*(12, 18)=12*18*6
입니다.Input: 4, 10, 16, 14 Output: 2
설명
둘 이상의 정수의 GCD는 두 숫자를 정확히 나눌 수 있는 가장 큰 정수입니다(나머지 없이).
예시
#include <iostream>
using namespace std;
int gcd(int a,int b) {
int temp;
while(b > 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a[] = {4, 10, 16, 14};
int n = 4;
int r = a[0];
for(int i=1; i<n; i++) {
r = gcd(r, a[i]);
}
cout << r << endl;
return 0;
} 출력
4