gcd函數簡介

大公因數（英語：highest common factor，hcf）也稱最大公約數（英語：greatest common divisor，gcd）是數學詞匯，指能夠整除多個整數的最大正整數。而多個整數不能都為零。例如8和12的最大公因數為4。
求兩個整數最大公約數主要的方法：
1.窮舉法：分別列出兩整數的所有約數，并找出最大的公約數。
2.素因數分解：分別列出兩數的素因數分解式，并計算共同項的乘積。
3.短除法：兩數除以其共同素因數，直到兩數互素時，所有除數的乘積即為最大公約數。
4.輾轉相除法：兩數相除，取余數重復進行相除，直到余數為0時，前一個除數即為最大公約數。
相關介紹： https://blog.csdn.net/Ljnoit/article/details/104730787
gcd函數寫法
C++寫gcd函數有幾種寫法，下面介紹幾種。
這些代碼我都對拍過，請大家放心使用。

1.while循環（常速）
?此段代碼a、b可以為0

inline int gcd(int a,int b) { int r; while(b>0){ r=a%b; a=b; b=r; } return a; }

?

2.三目運算符（較快）
?此段代碼a、b可以為0

inline int gcd(int a,int b) { return b>0 ? gcd(b,a%b):a; }

?

3.位運算（超快）
?此段代碼a、b不能為0

inline int gcd(int a,int b) { while(b^=a^=b^=a%=b); return a; }

?

4.if+while+位運算（超快）
?此段代碼a、b可以為0

inline int gcd(int a,int b) { if(b) while((a%=b) && (b%=a)); return a+b; }

5.輾轉相除法（較快）
?此段代碼a、b不能為0

inline int gcd(int a,int b) { if(a%b==0) return b; else return (gcd(b,a%b)); }

?

6.gcd庫函數（較慢）
?此段代碼a、b可以為0

#include <algorithm> inline int gcd(int a,int b) { return __gcd(a,b); }

————————————————
版權聲明：本文為CSDN博主「Ljnoit」的原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/Ljnoit/article/details/99319849

總結

以上是生活随笔為你收集整理的【C++】gcd函数的写法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。