Date: 2020dec24
Update: 2026sep21
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. Also recursive.
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.
// Uses our sqrt() function
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.
Example Uses:
#include <stdio.h>
int main() {
{ // pow
long result = pow(2, 8);
printf("2 ^ 8 = %ld\n", result);
long chk = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2;
printf("2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = %ld\n", chk);
putchar('\n');
}
{ // GCD
long result = gcd(21, 9);
printf("gcd(21, 9) = %ld\n", result);
putchar('\n');
}
{ // sqrt
long result = sqrt(81);
printf("sqrt(81) = %ld\n", result);
putchar('\n');
}
{ // isPrime
bool result = isPrime(27);
printf("isPrime(27) = %s\n", result ? "true" : "false");
// 3 * 3 * 3 = 27 (so its not prime)
putchar('\n');
}
{ // factorial
long result = factorial(5);
printf("factorial(5) = %ld\n", result);
long chk = 1 * 2 * 3 * 4 * 5;
printf("1 * 2 * 3 * 4 * 5 = %ld\n", chk);
putchar('\n');
}
}
Output:
2 ^ 8 = 256
2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256
gcd(21, 9) = 3
sqrt(81) = 9
isPrime(27) = false
factorial(5) = 120
1 * 2 * 3 * 4 * 5 = 120