# Overview

A few short algorithms play essential roles in multiple Project Euler problems.

Instead of writing them from scratch over and over again, I copy'n'paste'n'modify where appropriate.

My goal is that all solutions include only standard C++ library headers (or C++11/14/17/you-know-the-game).

They are "single-file-only" programs without external dependencies.

Therefore the snippets shown below are **NOT** put into a dedicated `toolbox.h`

file.

## List of algorithms:

# Greatest Common Divisor

// greatest common divisor
unsigned int gcd(unsigned int a, unsigned int b)
{
while (a != 0)
{
unsigned int c = a;
a = b % a;
b = c;
}
return b;
}

The Euclidean algorithm is a very efficient, simple (and surprisingly old !) algorithm. It's younger sibling, the binary GCD algorithm is supposed to be a tad bit faster, though.

**Note:** Some problems need `unsigned long long`

instead of `unsigned int`

.

**Note:** On newer versions of the GCC compiler there is a `__gcd(a, b)`

function in `#include <stl_algo.h>`

which might be faster on your computer.

(it's very likely that `std::gcd`

will be added to the C++ standard in the future)

# Least Common Multiple

// least common multiple
unsigned int lcm(unsigned int a, unsigned int b)
{
// parentheses avoid overflows for certain input values
return a * (b / gcd(a, b));
}

The Least Common Multiple builds upon the Greatest Common Divisor.

# Prime Sieves

## Sieve Of Eratosthenes

__Advantages:__

- faster than other simple sieves
- ok-ish memory consumption

__Disadvantages:__

- optimized version needs a dedicated lookup-function

#include <vector>
// odd prime numbers are marked as "true" in a bitvector
std::vector<bool> sieve;
// return true, if x is a prime number
bool isPrime(unsigned int x)
{
// handle even numbers
if ((x & 1) == 0)
return x == 2;
// lookup for odd numbers
return sieve[x >> 1];
}
// find all prime numbers from 2 to size
void fillSieve(unsigned int size)
{
// store only odd numbers
const unsigned int half = size >> 1;
// allocate memory
sieve.resize(half, true);
// 1 is not a prime number
sieve[0] = false;
// process all relevant prime factors
for (unsigned int i = 1; 2*i*i < half; i++)
// do we have a prime factor ?
if (sieve[i])
{
// mark all its multiples as false
unsigned int current = 3*i+1;
while (current < half)
{
sieve[current] = false;
current += 2*i+1;
}
}
}

My optimized code needs 0.5 bits per number which is less than what is required for the sieve based on trial division.

All prime numbers from 2 to 100 million can be found in about one third of a second.

A multi-threaded version is much faster, too.

## Based On Trial Division

__Advantages:__

- simple code
- can be computed in an incremental way ("on demand")

__Disadvantages:__

- slow division
- not very memory-efficient (allocation is slow, too !)

std::set<unsigned int> primes = { 2 };
for (unsigned int i = 3; i <= limit; i += 2)
{
bool isPrime = true;
// test against all prime numbers we have so far (in ascending order)
for (auto p : primes)
{
// next prime is too large to be a divisor ?
if (p*p > i)
break;
// divisible ? => not prime
if (i % p == 0)
{
isPrime = false;
break;
}
}
// yes, we have a prime number
if (isPrime)
primes.insert(i);
}

While `std::set`

offers some nice features "for free", such as looking up whether it contains an element,
its memory efficiency can be sub-prime.
In those cases I replace it by `std::vector`

and change both `insert`

s to `push_back`

.

Sometimes `std::unordered_set`

might be an option, too.

## Precomputed Tables

If code size and/or compilation times are no issue, then a precomputed table of prime numbers is certainly the fastest approach:

const unsigned int primes[] = {
#include "primes1000000.txt"
};

You can download these files from my server:

- all primes from 2 to 100 (0.1k)
- all primes from 2 to 1000 (0.6k)
- all primes from 2 to 10000 (5.8k)
- all primes from 2 to 100000 (54.8k)
- all primes from 2 to 1000000 (525.8k)

`primes100.txt`

looks like this:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

# Primality Tests

## Trial Division

This test is basically the same used in the Trial Division Prime Sieve, except that we don't know all smaller primes and therefore have to check against all odd numbers.

bool isPrime(unsigned int x)
{
// even number ? only even prime is 2
if ((x & 1) == 0)
return x == 2;
// check all even numbers from 3 to sqrt(x)
for (unsigned int i = 3; i*i <= x; i += 2)
if (x % i == 0)
return false;
// passed all tests, must be a prime number
return x > 1;
}

## Wheel Factorization

Wheel Factorization reduces the number of divisions
by observing that all prime factors can be expressed as:

`2, 3, 5`

or `any m: 30m+1, 30m+7, 30m+11, 30m+13, 30m+17, 30m+19, 30m+23, 30m+29`

(wheel size 30=2*3*5).

Some of these numbers are actually composite numbers (and not true prime factors) and therefore cause redundant work - but at least we don't forget about any prime factor.

More formally: this set of numbers contains all prime factors but is not minimal.

**Note:** running a Wheel-based primality test on all numbers from 1 to 10 million is roughly two times faster than with Trial Division

(1.8 vs. 3.3 seconds ... and only 1.4 seconds for the Miller-Rabin test).

bool isPrime(unsigned int x)
{
// prime test for 2, 3 and 5
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0)
return x == 2 || x == 3 || x == 5;
// wheel with size 30 (=2*3*5):
// test against 30m+1, 30m+7, 30m+11, 30m+13, 30m+17, 30m+19, 30m+23, 30m+29
// their deltas/increments are:
const unsigned int Delta[] = { 6, 4, 2, 4, 2, 4, 6, 2 };
// start with 7, which is 30*0+7
unsigned int i = 7;
// 7 belongs to the second test group
unsigned int pos = 1;
// check numbers up to sqrt(x)
while (i*i <= x)
{
// not prime ?
if (x % i == 0)
return false;
// skip forward to next test divisor
i += Delta[pos];
// next delta/increment
pos = (pos + 1) & 7;
}
// passed all tests, must be a prime number
return x > 1;
}

## Miller-Rabin Test

The Miller-Rabin test is a probabilistic primality test. Using specific *witnesses* it can be make a deterministic test for all 64 bit numbers.

My code needs the `mulmod`

and `powmod`

function also found on this page (see here).

// Miller-Rabin-test
bool isPrime(unsigned long long p)
{
// IMPORTANT: requires mulmod(a, b, modulo) and powmod(base, exponent, modulo)
// some code from https://ronzii.wordpress.com/2012/03/04/miller-rabin-primality-test/
// with optimizations from http://ceur-ws.org/Vol-1326/020-Forisek.pdf
// good bases can be found at http://miller-rabin.appspot.com/
// trivial cases
const unsigned int bitmaskPrimes2to31 = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) |
(1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) |
(1 << 23) | (1 << 29); // = 0x208A28Ac
if (p < 31)
return (bitmaskPrimes2to31 & (1 << p)) != 0;
if (p % 2 == 0 || p % 3 == 0 || p % 5 == 0 || p % 7 == 0 || // divisible by a small prime
p % 11 == 0 || p % 13 == 0 || p % 17 == 0)
return false;
if (p < 17*19) // we filtered all composite numbers < 17*19, all others below 17*19 must be prime
return true;
// test p against those numbers ("witnesses")
// good bases can be found at http://miller-rabin.appspot.com/
const unsigned int STOP = 0;
const unsigned int TestAgainst1[] = { 377687, STOP };
const unsigned int TestAgainst2[] = { 31, 73, STOP };
const unsigned int TestAgainst3[] = { 2, 7, 61, STOP };
// first three sequences are good up to 2^32
const unsigned int TestAgainst4[] = { 2, 13, 23, 1662803, STOP };
const unsigned int TestAgainst7[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022, STOP };
// good up to 2^64
const unsigned int* testAgainst = TestAgainst7;
// use less tests if feasible
if (p < 5329)
testAgainst = TestAgainst1;
else if (p < 9080191)
testAgainst = TestAgainst2;
else if (p < 4759123141ULL)
testAgainst = TestAgainst3;
else if (p < 1122004669633ULL)
testAgainst = TestAgainst4;
// find p - 1 = d * 2^j
auto d = p - 1;
d >>= 1;
unsigned int shift = 0;
while ((d & 1) == 0)
{
shift++;
d >>= 1;
}
// test p against all bases
do
{
auto x = powmod(*testAgainst++, d, p);
// is test^d % p == 1 or -1 ?
if (x == 1 || x == p - 1)
continue;
// now either prime or a strong pseudo-prime
// check test^(d*2^r) for 0 <= r < shift
bool maybePrime = false;
for (unsigned int r = 0; r < shift; r++)
{
// x = x^2 % p
// (initial x was test^d)
x = mulmod(x, x, p);
// x % p == 1 => not prime
if (x == 1)
return false;
// x % p == -1 => prime or an even stronger pseudo-prime
if (x == p - 1)
{
// next iteration
maybePrime = true;
break;
}
}
// not prime
if (!maybePrime)
return false;
} while (*testAgainst != STOP);
// prime
return true;
}

## Fermat Test

The Fermat primality test is neither fast nor accurate - but its implementation is quite short.

My code needs the `mulmod`

and `powmod`

function also found on this page (see here).

// return true if p is probably prime, accuracy depends on the number of iterations
// unfortunately, so-called Carmichael numbers pass all tests, see https://en.wikipedia.org/wiki/Carmichael_number
bool isPrime(unsigned long long p, unsigned int iterations = 90)
{
// fast check against small primes, eliminates a few Carmichael numbers, too
if (p < 2 || p % 2 == 0 || p % 3 == 0 || p % 5 == 0 || p % 7 == 0 || p % 11 == 0)
return p == 2 || p == 3 || p == 5 || p == 7 || p == 11;
// just a pseudo-random seed
unsigned long long a = p / 2 + 1;
// check p against several pseudo-random numbers
for (unsigned int i = 0; i < iterations; i++)
{
// we test against random numbers between 1 and p - 1 (inclusive)
// let's compute a simple hash: (i * 2654435761) % 2^32
// (Knuth's multiplicative hash)
a *= 2654435761;
if (a == 0 || a >= p)
a = a % (p - 1) + 1;
// Fermat found that for each prime: a^(p-1) % p == 1
if (powmod(a, p-1, p) != 1)
return false; // failed test, p is definitely not prime ...
}
// p is probably prime
return true;
}

# Modular Arithmetic

## Modular Multiplication

There are multiple versions of my modular arithmetic multiplication code (`mulmod`

) which solves `(a*b)%modulo`

code>.

The 32 bit version is extremely short:

// return (a*b) % modulo
unsigned int mulmod(unsigned int a, unsigned int b, unsigned int modulo)
{
return ((unsigned long long)a * b) % modulo;
}

The story is completely different for 64 bit because of a lack of standardized 128 bit integers in C/C++.

Bitwise multiplication is very similar to multiplication taught in school (and works only up to 63 bits):

// return (a*b) % modulo
unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long modulo)
{
// (a * b) % modulo = (a % modulo) * (b % modulo) % modulo
a %= modulo;
b %= modulo;
// fast path
if (a <= 0xFFFFFFF && b <= 0xFFFFFFF)
return (a * b) % modulo;
// we might encounter overflows (slow path)
// the number of loops depends on b, therefore try to minimize b
if (b > a)
std::swap(a, b);
// bitwise multiplication
unsigned long long result = 0;
while (a > 0 && b > 0)
{
// b is odd ? a*b = a + a*(b-1)
if (b & 1)
{
result += a;
result %= modulo;
// skip b-- because the bit-shift at the end will remove the lowest bit anyway
}
// b is even ? a*b = (2*a)*(b/2)
a <<= 1;
a %= modulo;
// next bit
b >>= 1;
}
return result;
}

The blockwise algorithm is an extension of the bitwise algorithm and multiplies multiple bits at once.

The 63-bit limit applies as well:

// return (a*b) % modulo
unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long modulo)
{
// (a * b) % modulo = (a % modulo) * (b % modulo) % modulo
a %= modulo;
b %= modulo;
// fast path
if (a <= 0xFFFFFFF && b <= 0xFFFFFFF)
return (a * b) % modulo;
// count leading zero bits of modulo
unsigned int leadingZeroes = 0;
unsigned long long m = modulo;
while ((m & 0x8000000000000000ULL) == 0)
{
leadingZeroes++;
m <<= 1;
}
// cover all bits of modulo
unsigned long long mask = (1 << leadingZeroes) - 1;
// bitwise multiplication
unsigned long long result = 0;
while (a > 0 && b > 0)
{
result += (b & mask) * a;
result %= modulo;
// next bits
b >>= leadingZeroes;
a <<= leadingZeroes;
a %= modulo;
}
return result;
}

A GCC-only version of `mulmod`

can be considerably faster:

unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long modulo)
{
// note: you can remove the following two lines
// but if (a*b)/c > 2^64 then the Assembler code will trigger a floating-point exception
a %= modulo;
b %= modulo;
// fast path
if (a <= 0xFFFFFFF && b <= 0xFFFFFFF)
return (a * b) % modulo;
// perform 128 bit arithmetic
#ifdef __x86_64__
// use GCC inline assembler
unsigned long long asmResult;
__asm__
(
"mulq %2\n" // result in rdx:rax
"divq %3" // quotient in rax, remainder in rdx
: "=&d" (asmResult), "+%a" (a)
: "rm" (b), "rm" (modulo)
: "cc" // clear conditions
);
return asmResult;
#else
// based on GCC's 128 bit implementation
return ((unsigned __int128)a * b) % modulo;
#endif
}

## Modular Exponentiation

`powmod`

solves `(base^exponent)%modulo`

and needs `mulmod`

. My algorithm is based on Exponentiation by squaring:

// return (base^exponent) % modulo
unsigned long long powmod(unsigned long long base, unsigned long long exponent, unsigned long long modulo)
{
unsigned long long result = 1;
while (exponent > 0)
{
// fast exponentation:
// odd exponent ? a^b = a*a^(b-1)
if (exponent & 1)
result = mulmod(result, base, modulo);
// even exponent ? a^b = (a*a)^(b/2)
base = mulmod(base, base, modulo);
exponent >>= 1;
}
return result;
}

# Big Integers

Working with very large numbers can be hard in C++ (whereas it's extremely simple in Java and Python).

Of course, there are dedicated C/C++ libraries, such as GMP, but I don't want to link/include external libraries.

Addition, subtraction and multiplication are straightforward implementations of basic school algorithms.

`MaxDigit`

can be set to other powers-of-10 in order to speed up the code but then the ''std::string'' functions will fail.

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are already solved and there wasn't a Hackerrank version of it (at the time I solved it) or I didn't care about it because it differed too much.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |