이것은 hcf를 찾는 좋은 방법입니까?

Question

#include <iostream> 
using namespace std; 
int main(){ 
    int a,b,hcf=0,i=1; 
    cout<<"Enter Value :"; 
    cin>>a; 

    cout<<"Enter value :"; 
    cin>>b; 

    while(i<=a || i<=b){ 
     if(a%i ==0 && b%i ==0)hcf=i; 
     ++i; 
     }   
return 0; 
    } 

또는 나머지 방법?

Answer 1

혹시 hcf를 찾으십니까? 숫자를 뒤집어 씌우는 것처럼 보입니다. 참여 숫자가 정말 작은 않는

Answer 2

은 유클리드의 알고리즘은 많은 빨리 될 가능성이 높습니다. 이 숫자는 숫자의 크기에 선형입니다 (반복마다 두 개의 구획이 있고, 구획은 가장 느린 유형의 명령 중 하나입니다). Euclid는 실제로 분석하기가 상당히 쉽습니다. Knuth V2에는 여러 페이지가 있지만 결론은 일반적으로 상당히 빠릅니다.

지금 사용하고있는 변형을 변형하려는 경우, 두 입력 중 더 작은 숫자와 동일한 i부터 시작하여 아래로으로 작업하십시오. 이렇게하면 첫 번째로 번 공통 요인을 찾을 수 있으므로 답을 얻을 수 있으므로 반복 할 수 있습니다.