首页 > 代码库 > PAT - 基础 - 最大公约数和最小公倍数

PAT - 基础 - 最大公约数和最小公倍数

2024-07-17 15:02:11   229人阅读

题目：

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式：

输入在一行中给出2个正整数M和N（<=1000）。

输出格式：

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例：

511 292

输出样例：

73 2044


两种方法
1、辗转相除法求最大公约数
流程如下：



算法
#include<stdio.h>#include<stdlib.h>int main(){	int M,N;	scanf("%d%d",&M,&N);		int ji=M*N;	int shang=M/N;	int yushu=M%N;	while(yushu!=0)   //辗转相除法	{		M=N;		N=yushu;		yushu=M%N;	}	printf("%d %d\n",N,ji/N);	system("pause");	return 0;}

　　

2 更相减损法

流程如下：


代码：
#include<stdio.h>#include<stdlib.h>int main(){	int M=0,N=0;	int temp=0;	int k=0;	scanf("%d%d",&M,&N);	if(M < N)	{		temp = M;		M = N;		N = temp;	}		temp = M *N;  // 更相减损术	while(M != N)	{		k= M-N;		if(k > N)		{			M = k;		}		else		{			M = N;			N = k;		}	}	temp = temp / M;	printf("%d%s%d",M," ", temp);	system("pause");}
　　






























        

            
                
                  
                
                

                    联系

                    我们