Date: 2020dec24 Language: C/C++ Keywords: integer Q. C/C++ pow, gcd, sqrt, isPrime, factorial - basic math functions A. pow - a number multiplied by itself n times - a ^ n

long pow(const long a, const long n) { if (n == 0) return 1; const long x = pow(a, n / 2); if (n % 2 == 0) { // its even return x * x; } else { return a * x * x; } } // Uses recursive calls to reduce the number of multiplications

GCD - Greatest Common Denominator

// Euler's method long gcd(const long a, const long b) { if (a == 0) return b; return gcd(b % a, a); } // So simple and elegant

Square Root

// Newton's method long sqrt(const long s) { long x0 = s / 2; if (x0 == 0) return s; long x1 = (x0 + s / x0) / 2; while(x1 < x0) { x0 = x1; x1 = (x0 + s / x0) / 2; } return x0; } // Basically a binary search

Is a number prime?

// By Soma Mbadiwe on https://stackoverflow.com/questions/15743192/check-if-number-is-prime-number bool isPrime(const long a) { if (a <= 1) return false; if (a == 2 || a == 3 || a == 5) return true; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0) return false; const long boundary = sqrt(a); for (long i = 6; i <= boundary; i += 6) { if (a % (i + 1) == 0 || a % (i + 5) == 0) { return false; } } return true; } // Since it can increment by 6 it gets the job done faster

Factorial

long factorial(const long n) { if (n <= 1) return 1; return factorial(n - 1) * n; } // Sadly, no smart tricks to make this efficient

These implementations are not the fastest but they have a first order of optimization.