最大公约数gcd和Win32版本实现

在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版本实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。