C語言求最大公約數最小公倍數(多種方法)
目錄
前言
- 這個求解方式多樣化,靈活變動,但是,網上沒有很好的資源和很全的程式碼,特此練習,敲打後,總結成本片文章.
單一求解
一.最大公約數
1.窮舉法(最簡單求解方式)
- 利用除法方式用當前的數字不斷去除以比較小的那個數的範圍,最後得到兩個數都可以整除的那個數.(這種方法也是最容易想到的)
核心程式碼
// 用比較小的一個數作為循環範圍,然後不斷減少,以便求出最後的公約數
void getResult(int a, int b, int min)
{
for (int i = min; i > 1; i--)
{
if (a%i == 0 && b%i == 0)
{
printf("%d %d的最大公約數是:%d\n", a, b, i);
}
}
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b, int min);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 用比較小的一個數作為循環範圍,然後不斷減少,以便求出最後的公約數
void getResult(int a, int b, int min)
{
for (int i = min; i > 1; i--)
{
if (a%i == 0 && b%i == 0)
{
printf("%d %d的最大公約數是:%d\n", a, b, i);
}
}
}
- 優化演算法
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b, int min);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 優化演算法
void getResult(int a, int b, int min) {
int temp = 0;
// 接收最小的值,對這個值進行操作,因為沒用指針,所以這裡用變數接收值修改
temp = min;
while (temp > 0)
{
if (a%temp == 0 && b%temp == 0)
{
break;
}
temp--;
}
printf("[%d %d]的最大公約數是:%d\n", a, b, temp);
}
2.遞減法操作
- 通過不斷的相減獲取最大公約數.
核心程式碼
// 優化演算法
void getResult(int a, int b, int min) {
int temp_A = 0;
int temp_B = 0;
// 接收最小的值,對這個值進行操作,因為沒用指針,所以這裡用變數接收值修改
temp_A = a;
temp_B = b;
while (temp_A != temp_B)
{
if (temp_A > temp_B)
{
temp_A = temp_A - temp_B;
}
else
{
temp_B = temp_B - temp_A;
}
}
printf("[%d %d]的最大公約數是:%d\n", a, b, temp_A);
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b, int min);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 優化演算法
void getResult(int a, int b, int min) {
int temp_A = 0;
int temp_B = 0;
// 接收最小的值,對這個值進行操作,因為沒用指針,所以這裡用變數接收值修改
temp_A = a;
temp_B = b;
while (temp_A != temp_B)
{
if (temp_A > temp_B)
{
temp_A = temp_A - temp_B;
}
else
{
temp_B = temp_B - temp_A;
}
}
printf("[%d %d]的最大公約數是:%d\n", a, b, temp_A);
}
3.輾轉相除法
- 不斷的讓兩個數做除法運算。其原理基於兩個整數的最大公約數等於其中較小的數和兩數的相除餘數的最大公約數
核心程式碼
// 優化演算法
void getResult(int a, int b, int min) {
int temp = 0;
int temp_A = 0;
int temp_B = 0;
// 接收最小的值,對這個值進行操作,因為沒用指針,所以這裡用變數接收值修改
temp_A = a;
temp_B = b;
while (temp_B != 0) // 餘數不為0，繼續相除，直到餘數為0
{
temp = temp_A % temp_B;
temp_A = temp_B;
temp_B = temp;
}
printf("[%d %d]的最大公約數是:%d\n", a, b, temp_A);
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b, int min);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 優化演算法
void getResult(int a, int b, int min) {
int temp = 0;
int temp_A = 0;
int temp_B = 0;
// 接收最小的值,對這個值進行操作,因為沒用指針,所以這裡用變數接收值修改
temp_A = a;
temp_B = b;
while (temp_B != 0) // 餘數不為0，繼續相除，直到餘數為0
{
temp = temp_A % temp_B;
temp_A = temp_B;
temp_B = temp;
}
printf("[%d %d]的最大公約數是:%d\n", a, b, temp_A);
}
4.遞歸法
核心程式碼
int gcd1(int x, int y) {
int temp = x % y;
if (temp == 0)
{
return y;
}
else
{
return(y, temp);
}
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b);
int gcd1(int x, int y);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 優化演算法
void getResult(int a, int b) {
int result = gcd1(a, b);
printf("[%d %d]的最大公約數是:%d\n", a, b, result);
}
int gcd1(int x, int y) {
int temp = x % y;
if (temp == 0)
{
return y;
}
else
{
return(y, temp);
}
}
5.位運演算法
核心程式碼
int gcd(int x, int y) {
// 交換x和y的值,然後進行y/x運算
while (x ^= y ^= x ^= y %= x);
return y;
}
- 其中
x ^= y ^= x ^= y %= x
- 翻譯為
假設 x=2;y=1;
拆分為：
x ^= y ^= x ^= y %= x
// 交換x和y的數字(這樣就把x=2;y=1;變為x=2;y=1;)
x^=y; // x = x ^ y;x的y次方 => x = 2 ^ 1; => x=2;
y^=x; // x = x ^ y;x的y次方 => y = 1 ^ 2; => y=1;
x^=y; // x = x ^ y;x的y次方 => x = 2 ^ 1; => x=2;
// y對x取模
y%=x; // y = y % x; y除以x的餘數 => y = 1%2 => y=2;
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b);
int gcd1(int x, int y);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, b);
}
else {
getResult(a, b,a);
}
}
// 優化演算法
void getResult(int a, int b) {
int result = gcd1(a, b);
printf("[%d %d]的最大公約數是:%d\n", a, b, result);
}
int gcd1(int x, int y) {
// 交換x和y的值,然後進行y/x運算
while (x ^= y ^= x ^= y %= x);
return y;
}
二.最小公倍數
1.窮舉法
核心程式碼
void getResult(int a, int b,int max) {
int temp = 0;
for (int i = max; i <= (a*b); i++)
{
if (i%a == 0 && i%b == 0)
{
temp = i;
break;
}
}
printf("[%d %d]的最小公倍數是:%d\n", a, b, temp);
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b, int max);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b, a);
}
else {
getResult(a, b,b);
}
}
// 優化演算法
void getResult(int a, int b,int max) {
int temp = 0;
for (int i = max; i <= (a*b); i++)
{
if (i%a == 0 && i%b == 0)
{
temp = i;
break;
}
}
printf("[%d %d]的最小公倍數是:%d\n", a, b, temp);
}
2.輾轉相除法
核心程式碼
// 優化演算法
void getResult(int a, int b) {
// 用於自增的變數
int temp = 0;
// 接收最小公倍數最後的結果
int gongbei = 0;
// ===== 沒有使用指針,所以,採用用變數接收修改參數值的方法 ******
temp = a;
// 獲取兩個數中較大的一個
gongbei = a;
while (1)
{
// 兩個數中較大的數除以較小的數,能除開就說明最大的數就是兩個數的最小公倍數
if (gongbei%b == 0) {
break;
}
// 較大的數除不開較小的數,最大的數就再加一個自己再循環除第二個數
// 累加獲得最小公倍數
gongbei += temp;
}
printf("[%d %d]的最小公倍數是:%d\n", a, b, gongbei);
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b);
}
else {
getResult(a, b);
}
}
// 優化演算法
void getResult(int a, int b) {
// 用於自增的變數
int temp = 0;
// 接收最小公倍數最後的結果
int gongbei = 0;
// ===== 沒有使用指針,所以,採用用變數接收修改參數值的方法 ******
temp = a;
// 獲取兩個數中較大的一個
gongbei = a;
while (1)
{
// 兩個數中較大的數除以較小的數,能除開就說明最大的數就是兩個數的最小公倍數
if (gongbei%b == 0) {
break;
}
// 較大的數除不開較小的數,最大的數就再加一個自己再循環除第二個數
// 累加獲得最小公倍數
gongbei += temp;
}
printf("[%d %d]的最小公倍數是:%d\n", a, b, gongbei);
}
3.通過公約數獲取
核心程式碼
int function_my(int x, int y) {
return x * y / gcd1(x, y);
}
完整程式碼
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b);
int gcd1(int x, int y);
int function_my(int x, int y);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
if (a > b)
{
getResult(a, b);
}
else {
getResult(a, b);
}
}
// 優化演算法
void getResult(int a, int b) {
int result = function_my(a, b);
printf("[%d %d]的最小公倍數是:%d\n", a, b, result);
}
int gcd1(int x, int y) {
// 交換x和y的值,然後進行y/x運算
while (x ^= y ^= x ^= y %= x);
return y;
}
int function_my(int x, int y) {
return x * y / gcd1(x, y);
}
合併求解
最大公約和最小公倍一起求
#define _CRT_SECURE_NO_WARNINGS 1
// 此文件包含 "main" 函數。程式執行將在此處開始並結束。
//
#include <stdio.h>
#include <stdlib.h>
void maxCommonNumber();
void getResult(int a, int b);
int gcd1(int x, int y);
int function_my(int x, int y);
int main()
{
maxCommonNumber();
system("pause");
return 0;
}
void maxCommonNumber() {
int a = 0;
int b = 0;
int result = 0;
printf("請輸入兩個數:\n");
printf("請輸入第一個數a:");
scanf("%d", &a);
printf("請輸入第二個數b:");
scanf("%d", &b);
getResult(a, b);
}
// 結果
void getResult(int a, int b) {
int yue = gcd1(a, b);
printf("[%d %d]最大公約數:%d\n", a, b, yue);
int bei = function_my(a, b);
printf("[%d %d]最小公倍數:%d\n", a, b, bei);
}
int gcd1(int x, int y) {
// 交換x和y的值,然後進行y/x運算
while (x ^= y ^= x ^= y %= x);
return y;
}
int function_my(int x, int y) {
return x * y / gcd1(x, y);
}
