C趣味編程百例(13)公約數(shù)和最小公倍數(shù)

字號： 小 中 大

42.公約數(shù)和最小公倍數(shù)
     求任意兩個正整數(shù)的公約數(shù)和(GCD)和最小公倍數(shù)(LCM)
    *問題分析與算法設(shè)計
     手工方式求兩個正整數(shù)的蝚大公約數(shù)的方法是用輾轉(zhuǎn)相除法，在程序中可以模擬這種方式。
    *程序與程序注釋
    #include
    void main()
    {
     int a,b,num1,num2,temp;
     printf("Input a & b:");
     scanf("%d%d",&num1,&num2);
     if(num1>num2) /*找出兩個數(shù)中的較大值*/
     {
     temp=num1; num1=num2; num2=temp; /*交換兩個整數(shù)*/
     }
     a=num1; b=num2;
     while(b!=0) /*采用輾轉(zhuǎn)相除法求公約數(shù)*/
     {
     temp=a%b;
     a=b;
     b=temp;
     }
     printf("The GCD of %d and %d is: %d\n",num1,num2,a); /*輸出公約數(shù)*/
     printf("The LCM of them is: %d\n",num1*num2/a); /*輸出最小公倍數(shù)*/
    }
    *運行結(jié)果
     1.Input a & b: 20 55
     The GCD of 20 and 55 is: 5
     The LCM of them is: 220
     2.Input a & b: 17 71
     The GCD of 17 and 71 is: 1
     The LCM of them is: 1207
     3.Input a & b: 24 88
     The GCD of 24 and 88 is: 8
     The LCM of them is: 264
     4.Input a & b: 35 85
     The GCD of 35 and 85 is: 5
     The LCM of them is: 595
    *思考題
     求一個最小的正整數(shù)，這個正整數(shù)被任意n(2<=n<=10)除都是除不盡的，而且余數(shù)總是(n-1)。例如：被9除時的余數(shù)為8。要求設(shè)計一個算法，不允許枚舉與除2、除3、....、除9、除10有關(guān)的命令，求出這個正整數(shù)。