#include<iostream> //gcd the hard way :D
#include <vector>
using namespace std;
int main()
{
int a;
int b;
vector<int> r;
vector<int> m;
cin >> a >> b;
for (int i = 1; i <= a; i++)
{
if (a % i == 0)
{
r.push_back(i);
}
}
for (int i = 1; i <= b; i++)
{
if (b % i == 0)
{
m.push_back(i);
}
}
// for finding the max ---->
int gcd = 1;
for (int i = 0; i < r.size(); i++)
{
for (int j = 0; j < m.size(); j++)
{
if (r[i] == m[j])
{
if (r[i] > gcd)
{
gcd = r[i];
}
}
}
}
cout << "the gcd is: " << gcd;
return 0;
}🥸حالا اگر بخوایم الگوریتم اقلیدسی بریم کارمون خیلی راحت‌تر میشه و تو کمتر از بیست خط کار جمعه. البته اینجا از روش تفریق استفاده نکردیم چون کار با باقیمانده راحت‌تره.
#include <iostream>//الگوریتم اقلیدسی
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
int x=a, y=b;
int temp;
while(y != 0)
{
temp = y;
y = x%y;
x = temp;
}
cout<<"the gcd is: "<<x<<endl;
return 0;
}
البته یک روش دیگه هم وجود داره که با استفاده از عامل‌های اول اعداد ب‌م‌‌م رو پیدا کنیم که باز هم به بهینه بودن الگوریتم اقلیدسی نیست🥸
#math_ideas
#math_facts
#coding
@mathloopinfinite