在RSA這一類型的加密算法實現程序里，常常見到一個函數名字為gcd()。

這個是啥？

Gcd，最大公約數。

如果數a能被數b整除，a就叫做b的倍數，b就叫做a的約數。

最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。
a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c）。
求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。
與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。

手算；
（8，9）=1，
（18，3）=3，
（12，16）=4，

輾轉相除法C語言Win32實現如下；

#include <windows.h> #include "resource.h"LRESULT CALLBACK WindowProcedure (HWND, UINT, WPARAM, LPARAM); int gcd(int ,int );HINSTANCE hInst; TCHAR szClassName[] = TEXT("gcdDemo");int WINAPI WinMain (HINSTANCE hThisInstance,HINSTANCE hPrevInstance,LPSTR lpszArgument,int nFunsterStil) {HWND hwnd;MSG messages;WNDCLASSEX wincl;hInst = hThisInstance;wincl.hInstance = hThisInstance;wincl.lpszClassName = szClassName;wincl.lpfnWndProc = WindowProcedure;wincl.style = CS_DBLCLKS;wincl.cbSize = sizeof (WNDCLASSEX);wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION);wincl.hIconSm = LoadIcon (NULL, IDI_APPLICATION);wincl.hCursor = LoadCursor (NULL, IDC_ARROW);wincl.lpszMenuName = MAKEINTRESOURCE (IDC_GCDDEMO);wincl.cbClsExtra = 0;wincl.cbWndExtra = 0;wincl.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);if (!RegisterClassEx (&wincl))return 0;hwnd = CreateWindowEx (0,szClassName,TEXT("最大公約數 Demo"),WS_OVERLAPPEDWINDOW,CW_USEDEFAULT,CW_USEDEFAULT,300,200,HWND_DESKTOP,NULL,hThisInstance,NULL);ShowWindow (hwnd, nFunsterStil);while (GetMessage (&messages, NULL, 0, 0)){TranslateMessage(&messages);DispatchMessage(&messages);}return messages.wParam; }LRESULT CALLBACK WindowProcedure (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam) {PAINTSTRUCT ps;HDC hdc;RECT rt; char szBuffer[100]; int m1=8,n1=9;int m2=18,n2=3;int m3=12,n3=16;switch (message){case WM_COMMAND:switch (LOWORD(wParam)){case IDM_gcd: hdc=GetDC(hwnd);wsprintf(szBuffer, "8和9的gcd是：%d",gcd(m1,n1));TextOut(hdc,50,20,szBuffer,lstrlen(szBuffer));wsprintf(szBuffer, "18和3的gcd是：%d",gcd(m2,n2));TextOut(hdc,50,50,szBuffer,lstrlen(szBuffer));wsprintf(szBuffer, "12和16的gcd是：%d",gcd(m3,n3));TextOut(hdc,50,80,szBuffer,lstrlen(szBuffer));break;case IDM_ABOUT:MessageBox (hwnd, TEXT ("gcdDemo v1.0\nCopyright (C) 2020\n by bo"),TEXT ("gcdDemo"), MB_OK | MB_ICONINFORMATION);break;case IDM_EXIT:DestroyWindow(hwnd);break;default:return DefWindowProc(hwnd, message, wParam, lParam); }break;case WM_CREATE:break;case WM_PAINT:hdc = BeginPaint(hwnd, &ps); GetClientRect(hwnd, &rt); EndPaint(hwnd, &ps);break;case WM_DESTROY:PostQuitMessage (0);break;default:return DefWindowProc (hwnd, message, wParam, lParam);}return 0; }int gcd(int a,int b) {int temp;while(b){ /*利用輾除法，直到b為0為止*/temp = b;b = a % b;a = temp;}return a; }

運行；

工程；

資源和頭文件；

#include "resource.h" #include <windows.h>/ // // Menu //IDC_GCDDEMO MENU BEGINPOPUP "&File"BEGINMENUITEM "最大公約數Demo", IDM_gcdMENUITEM "E&xit", IDM_EXITENDPOPUP "&Help"BEGINMENUITEM "&About ...", IDM_ABOUTEND END #define IDM_EXIT 10001 #define IDM_ABOUT 10002#define IDC_GCDDEMO 10101 #define IDD_ABOUTBOX 10102 #define IDM_gcd 40001

?

總結

以上是生活随笔為你收集整理的最大公约数gcd和Win32版本实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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