[C/C++ 演算法]- 最大公因數、最小公倍數、因數分解
[C/C++ 演算法]- 最大公因數、最小公倍數、因數分解
剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。
拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/GCDPNumber.htm
#include <stdio.h>
#include <stdlib.h>
int gcd(int m, int n) {
while(n != 0) {
int r = m % n;
m = n;
n = r;
}
return m;
}
int lcm(int m, int n) {
return m * n / gcd(m, n);
}
int main(void) {
int m, n;
printf("輸入兩數：");
scanf("%d %d", &m, &n);
printf("Gcd：%d\n", gcd(m, n));
printf("Lcm：%d\n", lcm(m, n));
return 0;
}
|
One thought on “[C/C++ 演算法]- 最大公因數、最小公倍數、因數分解”
您好，可以請您詳細解釋程式碼嗎？看不大懂，但是執行是正確的！謝謝您！
版主回覆：(08/31/2015 01:27:50 PM)
以下是「http://openhome.cc/Gossip/AlgorithmGossip/GCDPNumber.htm」說明內容
可整除兩數的稱之為公因數，可使用輾轉相除法來求最大公因數，可被兩數整除的某數稱之為公倍數，兩數的最大公因數乘最小公倍數正好等於兩數乘積。因數分解就是求某數的所有因數。
解法
因數分解就是使用小於輸入數的數值當作除數，去除以輸入數值，如果可以整除就視為因數。