Cプログラミング
 Computer >> コンピューター >  >> プログラミング >> Cプログラミング

ユークリッドの互除法を実装するためのCプログラム


問題

ユークリッドのアルゴリズムを実装して、2つの整数の最大公約数(GCD)と最小公倍数(LCM)を見つけ、指定された整数とともに結果を出力します。

解決策

ユークリッドのアルゴリズムを実装して、2つの整数の最大公約数(GCD)と最小公倍数(LCM)を見つけるソリューションは次のとおりです-

GCDとLCMを見つけるために使用されるロジックは次のとおりです-

if(firstno*secondno!=0){
   gcd=gcd_rec(firstno,secondno);
   printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
   printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
}

呼び出される関数は次のとおりです-

int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}
を返します

プログラム

以下は、2つの整数の最大公約数(GCD)と最小公倍数(LCM)を見つけるためにユークリッドのアルゴリズムを実装するCプログラムです

#include<stdio.h>
int gcd_rec(int,int);
void main(){
   int firstno,secondno,gcd;
   printf("Enter the two no.s to find GCD and LCM:");
   scanf("%d%d",&firstno,&secondno);
   if(firstno*secondno!=0){
      gcd=gcd_rec(firstno,secondno);
      printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
      printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
   }
   else
      printf("One of the entered no. is zero:Quitting\n");
   }
   /*Function for Euclid's Procedure*/
   int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}
を返します

出力

上記のプログラムを実行すると、次の結果が得られます-

Enter the two no.s to find GCD and LCM:4 8

The GCD of 4 and 8 is 4

The LCM of 4 and 8 is 8

  1. バブルソートを実装するC++プログラム

    バブルソートは、比較ベースのソートアルゴリズムです。このアルゴリズムでは、隣接する要素が比較および交換されて、正しいシーケンスが作成されます。このアルゴリズムは他のアルゴリズムよりも単純ですが、いくつかの欠点もあります。このアルゴリズムは、多数のデータセットには適していません。並べ替えタスクの解決には時間がかかります。 バブルソート手法の複雑さ 時間計算量:最良の場合はO(n)、O(n 2 )平均および最悪の場合 スペースの複雑さ:O(1) Input − A list of unsorted data: 56 98 78 12 30 51 Output &mi

  2. 基数ソートを実装するC++プログラム

    基数ソートは、非比較ソートアルゴリズムです。この並べ替えアルゴリズムは、同じ位置と値を共有する数字をグループ化することにより、整数キーで機能します。基数は、記数法のベースです。 10進法では、基数または基数は10であることがわかっているので、いくつかの10進数を並べ替えるには、数値を格納するために10個の位取りボックスが必要です。 基数ソート手法の複雑さ 時間計算量:O(nk) スペースの複雑さ:O(n + k) Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output &minus