Last active
January 10, 2020 19:34
-
-
Save misterpoloy/3fdc11cfc951a11fde153052b6c2c9f6 to your computer and use it in GitHub Desktop.
GCD using Euclid's algorithm (mcd) in c++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://www.youtube.com/watch?v=7HCd074v8g8&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25&index=8&t=0s | |
#include <iostream> | |
#include <list> | |
#include <cmath> | |
int brutDivision(int a, int b) { | |
int gcd = 1; | |
std::list<int> factors; | |
for (int i = 2; i < sqrt(a); i++) { | |
if (a % i == 0) { | |
factors.push_back(i); | |
factors.push_back(a / i); | |
} | |
}; | |
for (int factor: factors) { | |
if (factor > gcd) | |
gcd = factor; | |
} | |
return gcd; | |
} | |
int euclids(int a, int b) { | |
int dividend = a > b ? a : b; | |
int divisor = a < b ? a : b; | |
while (divisor != 0) { | |
int remainder = dividend / divisor; | |
dividend = divisor; | |
divisor = remainder; | |
} | |
return dividend; | |
} | |
int main() { | |
int a = 105; | |
int b = 350; | |
std::cout << brutDivision(a, b) << std::endl; | |
std::cout << euclids(a, b) << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment