【经典100题】题目16 求两个数的最大公约数和最小公倍数

喜欢ヅ旅行 2022-04-08 11:29 216阅读 0赞

# 题目 #

求两个数的最大公约数和最小公倍数。

最大公约数：指两个或多个整数共有约数中最大的一个

最小公倍数：指两个或多个整数共有倍数中最小的一个

**说明：自己没有搞清楚最大公约数和最小公倍数的定义，结果走了不少弯路，下面的解法是一种比较简单但是效率的不高的解法。可以参考“辗除法”，在后续会学习一下。**

--------------------

# C语言实现 #

#include<stdio.h>
    
    void zuidagongyinshu(int x, int y);
    void zuixiaogongbeishu(int x, int y);
    
    void main()
    {
    	int a, b;
    	printf("请输入正整数a：");
    	scanf("%d", &a);
    	printf("请输入正整数b：");
    	scanf("%d", &b);
    	zuidagongyinshu(a, b);
    	zuixiaogongbeishu(a, b);
    	
    }
    
    void zuidagongyinshu(int x, int y)
    {
    	//找出最小的数
    	int small;
    	if (x > y)
    		small = y;
    	else
    		small = x;
    	while (small!=0)
    	{
    		if (x%small == 0 && y%small == 0)
    		{
    			printf("最大公因数是：%d\n", small); 
    			break;
    		}
    		small--;
    	}
    }
    
    void zuixiaogongbeishu(int x, int y) 
    {
    	//找出最大的数
    	int big;
    	if (x < y)
    		big = y;
    	else
    		big = x;
    	while (1)
    	{
    		if (big%x == 0 && big%y == 0)
    		{
    			printf("最小公倍数是：%d\n", big); 
    			break;
    		}
    		big++;
    	}
    }

运行结果：

> 请输入正整数a：270  
> 请输入正整数b：36  
> 最大公因数是：18  
> 最小公倍数是：540  
> 请按任意键继续. . .

--------------------

# python实现 #

#最大公因数
    def zuidagongyinshu(x, y):
        #找出最小的数
        if x > y:        
            small = y
        else:        
            small = x
        
        
        while small !=0:
            if x%small == 0 and y%small == 0:
                print("最大公因数%d"%small )
                break
            small -=1
    
    #最小公倍数        
    def zuixiaogongbeishu(x,y):
        #找出最大的数
        if x > y:
            big = x        
        else:
            big = y
            
        while(1):
            if big%x == 0 and big%y == 0:
                print("最小公倍数：%d"%big)
                break
            big+=1
    
    #主程序       
    a =int(input("请输入正整数a："))
    b =int(input("请输入正整数b："))
    zuidagongyinshu(a, b)
    zuixiaogongbeishu(a,b)

运行结果：

> 请输入正整数a：36  
> 请输入正整数b：270  
> 最大公因数18  
> 最小公倍数：540

--------------------

★ finished by songpl,2018.12.13