這是找到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

除非涉及到的數字真的小，歐幾里德的算法很可能是一個很多更快。這個數字的大小是線性的（每次迭代有兩個分區，分區是最慢的指令類型之一）。歐幾里德的分析實際上是相當不重要的 - Knuth V2上有幾個頁面，但底線是它通常比較快。

如果你想使用現在使用的變體，我會從i開始等於兩個輸入中較小的一個，然後按照你的方法下降。這樣，第一次時間你找到一個共同的因素，你有你的答案，所以你可以跳出循環。