Skip to content

Instantly share code, notes, and snippets.

@SergeyNarozhny
Last active April 13, 2017 22:38
Show Gist options
  • Save SergeyNarozhny/30af46f148f55a8772151198e28f2a64 to your computer and use it in GitHub Desktop.
Save SergeyNarozhny/30af46f148f55a8772151198e28f2a64 to your computer and use it in GitHub Desktop.
#include <cassert>
#include <cstdint>
#include <iostream>
template <class Int>;
Int gcd(Int a, Int b) {
assert(a > 0 && b > 0);
Int current_gcd = 1;
for (Int d = 1; d * d <= a; d++) {
if (a % d == 0) {
if (b % d == 0) {
current_gcd = d;
}
Int big_d = a / d;
if (b % big_d == 0) {
return big_d;
}
}
}
return current_gcd;
}
int main(void) {
std::int64_t a, b;
std::cin >> a >> b;
std::cout << gcd(a, b) << std::endl;
}
@SergeyNarozhny
Copy link
Author

Second revision uses assumption:
min(d1,d2) <= sqrt(a); max(d1,d2) >= sqrt(a); d2 = a / d1;

@SergeyNarozhny
Copy link
Author

Or using Euclidean:
while (a > 0 && b > 0) { if (a > b) { a %= b; } else { b %= a; } } return a == 0 ? b : a;

@SergeyNarozhny
Copy link
Author

Or simplifying and using swap inside Euclidean while:
while (b > 0) { a %= b; std::swap(a, b); } return a;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment