Математика и теория чисел (НОД, решето, модульная арифметика)

Алгоритм Евклида сжимает пару (a, b) до (b, a mod b), пока остаток не станет 0; то, что осталось, и есть наибольший общий делитель. Решето перечисляет простые числа до n, а модульная арифметика удерживает огромные ответы в фиксированном диапазоне: другие явные математические инструменты этого семейства.

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}

a, b до ~1e18 для GCD Евклида (O(log(min(a,b))) шагов), n до ~1e6..1e7 для решета простых чисел -> O(n log log n); модульное возведение в степень a^b mod m работает за O(log b).