둘 이상의 숫자의 GCD를 찾는 방법은 무엇입니까?

일반적으로 프로그래밍에는 고급 수학 개념에 대한 지식이 필요하지 않지만 기본 수학 지식을 갖는 것은 특히 경쟁 프로그래밍(CP)의 경우 항상 도움이 됩니다.

유용할 수 있는 몇 가지 개념과 요령을 배우는 것은 나쁘지 않습니다. 이러한 개념 중 하나는 둘 이상의 숫자의 최대 공약수(GCD)를 찾는 것입니다. 직접 사용되지 않을 수도 있지만 여전히 프로그래밍을 사용하여 수학적 문제를 해결하는 방법에 대한 기본 아이디어를 제공할 수 있습니다.

수학에서 모두 0이 아닌 두 개 이상의 정수의 최대공약수라고도 하는 최대공약수(GCD)는 각각의 정수를 나누는 가장 큰 양의 정수입니다. 두 정수 x, y에 대해 x와 y의 최대 공약수는 gcd(x,y)로 표시됩니다. 예를 들어 gcd(8,12)는 4가 8과 12를 모두 나누는 가장 큰 양수이므로 4입니다.

GCD의 응용

GCD는 간단하고 복잡한 여러 응용 프로그램에 사용됩니다. 사실, 분수를 단순화할 때 GCD를 인식하지 않고 암묵적으로 GCD를 계산했을 것입니다. 분수를 줄이는 것은 분자와 분모를 모두 GCD로 나누는 문제입니다.

GCD는 RSA와 같은 암호화 체계에서 매우 중요한 모듈러 역수를 계산하기 위해 확장된 유클리드 알고리즘에서도 사용됩니다. 따라서 암호학에서 중요한 도구입니다.

C++를 사용하여 2개 이상의 숫자의 GCD를 찾는 프로그램을 작성할 것입니다. 항상 그렇듯이 이 문제를 해결하는 방법에는 여러 가지가 있으며 그 중 2~3가지에 대해 논의할 것입니다.

1. for 루프와 if 문을 사용하는 GCD

이 방법은 1부터 시작하여 알아내야 하는 GCD가 있는 가장 작은 숫자까지 모든 숫자를 반복하므로 Brute Force 접근 방식으로 간주할 수 있습니다. 그런 다음 각 숫자에 대해 모든 숫자를 완전히 나누는지 확인합니다. 그렇다면 gcd라고 부르고 다음 숫자로 이동하여 전체를 완전히 나누는 가장 큰 숫자가 필요하므로 프로세스를 반복합니다.



노트:

아래 코드는 2개의 숫자에만 적용됩니다. 각 숫자를 2개가 아닌 모든 숫자로 나누거나 처음 2개의 숫자와 다음 숫자의 gcd로 gcd 함수를 반복해서 호출하고 이 과정을 반복하여 n개의 숫자에 대해 일반화할 수 있습니다.

#include <iostream>
using namespace std;
int gcd(int n1, int n2){
    int gcd, i;
    for(i=1; i <= n1 && i <= n2; ++i){
        // Checks if i is factor of both integers
        if(n1 % i == 0 && n2 % i == 0)
            gcd = i;
    }
    return gcd;
}

int main(){
    int n1, n2, res;

    cout<<"Enter two integers: \n";
    cin>>n1>>n2;

    res = gcd(n1, n2);

    cout<<"G.C.D of "<<n1<<" and "<<n2<<" is "<<res;

    return 0;
}

2. while 루프와 if 문을 사용한 GCD

이것은 GCD를 찾는 더 좋은 방법입니다. 이 방법은 큰 정수에서 작은 정수를 빼서 그 결과를 큰 정수를 담고 있는 변수에 대입하는 방식입니다. 이 과정은 n1과 n2가 같을 때까지 계속됩니다.



노트:
아래 코드는 2개의 숫자에만 적용됩니다. 처음 2개의 숫자와 다음 숫자의 gcd로 gcd 함수를 반복해서 호출하고 이 과정을 반복함으로써 n개의 숫자에 대해서도 일반화할 수 있습니다.

#include <iostream>
using namespace std;

int gcd(int n1, int n2){
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }

    return n1;
}

int main()
{
    int n1, n2, res;

    cout<<"Enter two integers: \n";
    cin>>n1>>n2;

    res = gcd(n1, n2);

    cout<<"G.C.D of "<<n1<<" and "<<n2<<" is "<<res;

    return 0;
}

아래 의견에 의견을 공유하고 기사가 마음에 들면 엄지 손가락을 치십시오.

내 블로그https://codeunlock.in/를 확인하여 다른 기사를 읽을 수 있습니다.