दो नंबर का जीसीडी


कठिनाई स्तर आसान
में अक्सर पूछा एसएपी एसएपी लैब्स टीसीएस
GCD एलसीएम मठ स्कूल प्रोग्रामिंग

क्या है सबसे बड़ा साझा कारक? दो संख्याओं का GCD सबसे बड़ी संख्या है जो दोनों को विभाजित करता है।

दृष्टिकोण -1

जानवर सेना

सभी को खोजना मुख्य दोनों संख्याओं के कारक, फिर प्रतिच्छेदन का गुणनफल ज्ञात करना।

दोनों संख्याओं को विभाजित करने वाली सबसे बड़ी संख्या ज्ञात करना।

ऐसा क्या है जो हम उसी के लिए करते हैं?

  • दो संख्याओं में से छोटी संख्या ज्ञात कीजिए
    • क्यों?
    • उदाहरण -4,6।
      • 6 के सभी कारकों की गणना करने में कोई मतलब नहीं है जब सबसे बड़ा प्रमुख कारक 4 से कम होगा
  • छोटी संख्या में 1 से एक लूप चलाएं
  • उत्तर रखने के लिए एक चर बनाए रखें
  • यदि कोई संख्या दोनों संख्याओं को विभाजित करती है तो हम बस चर को अद्यतन करते हैं

छोटी प्रक्रिया का पालन करें और दोनों नंबरों के सबसे बड़े प्रमुख कारक के साथ अंत करें!

फिर भी, कुलबुलाहट? कोड में देखो!

दो नंबर के जीसीडी के लिए जावा कोड

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    int ans=1;
    int num=0;
    if(num1>num2)
      num=num2;
    else
      num=num1;
    for(int i=num;i>0;i--)
    {
      if(num1%i==0 && num2%i==0)
      {ans=i;break;}
    }
    return ans;
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,28);
    System.out.println(gcd);
  }
}

दो नंबर के GCD के लिए C ++ कोड

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  int ans=1; 
  int num=0; 
  if(num1>num2) 
    num=num2; 
  else 
    num=num1; 
  for(int i=num;i>0;i--) 
  { 
    if(num1%i==0 && num2%i==0) 
      {ans=i;break;} 
  } 
  return ans;
}
int main()
{
  int gcd=find_fac(12,28);
  cout<<gcd;
}
4

दो नंबर की जीसीडी के लिए जटिलता विश्लेषण

समय जटिलता = O (n)

दृष्टिकोण -2

जीसीडी के लिए यूक्लिडियन एल्गोरिथ्म का उपयोग करना

एल्गोरिथम सिद्धांत द्वारा: HCF छोटे से एक बड़ी संख्या को घटाने पर नहीं बदलता है।

हम जानते हैं कि बार-बार घटाव = विभाजन

एक ही समस्या के साथ स्मार्ट होने के लिए तीन सुनहरे नियमों का पालन करना चाहिए।

उन्हें अपने सिर में फिट करें और उन्हें मूल समझें!

  • जीसीडी (ए, बी) = जीसीडी (बी, ए) अगर बी> ए
  • जीसीडी (ए, बी) = जीसीडी (ए, एक% बी)
  • जीसीडी (ए, 0) = ए

यदि यह आपके लिए एक बार में बहुत अधिक है, तो चिंता न करें, मेरे पास आपके लिए एक छोटा सा फ्लोचार्ट है।

दो नंबर का जीसीडी
फ्लोचार्ट दो संख्याओं का GCD दिखा रहा है, जहाँ पहली संख्या 10 है और दूसरी संख्या 14 है

फ्लोचार्ट में उदाहरण- (10,14)

  • हम GCD (14,10) को 14> 10 के रूप में पाते हैं
    • जीसीडी (14,10) = जीसीडी (14% 10,10)
  • (4,10) की जीसीडी की गणना के लिए काम करें
  • (10,4) के एचसीएफ की गणना 10> 4 के रूप में की जाएगी
    • एचसीएफ (10,4) = जीसीडी (10% 4,4) = जीसीडी (2,4)
  • 4,2> 4 के रूप में GCD (2) का पता लगाएं
    • एचसीएफ (4,2) = जीसीडी (4% 2,2) = जीसीडी (2,2)
  • जीसीडी (2,2) = एचसीएफ (0,2)
  • जैसा कि हमने 0.Voila को मारा, हमारे पास हमारा उत्तर है! 2

दो नंबर के जीसीडी के लिए जावा प्रोग्राम

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    if(num2==0)
      return num1;
    if(num1>num2)
      return find_fac(num1%num2,num2);
    else
      return find_fac(num2,num1);
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,24);
    System.out.println(gcd);
  }
}

दो नंबर के GCD के लिए C ++ कोड

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  if(num2==0)
      return num1;
  if(num1>num2)
      return find_fac(num1%num2,num2);
  else
      return find_fac(num2,num1);
}
int main()
{
  int gcd=find_fac(12,24);
  cout<<gcd;
}
12

दो नंबर की जीसीडी के लिए जटिलता विश्लेषण

समय जटिलता = O (लॉग (n))

जहाँ n दोनों संख्याओं का न्यूनतम है

ये संख्याओं के HCF को खोजने के तरीके थे!

कैसे के बारे में हम एक समस्या पर कौशल फ्लेक्स और अधिक जटिल सामान जानने के लिए?

Eratosthenes की छलनी!

एराटोस्थनीज की छलनी