1function fastPow(base, exp, mod) {
2 let result = 1;
3 base = base % mod;
4 while (exp > 0) {
5 if (exp & 1) result = (result * base) % mod;
6 base = (base * base) % mod;
7 exp >>= 1;
8 }
9 return result;
10}
11function gcd(a, b) {
12 while (b !== 0) {
13 [a, b] = [b, a % b];
14 }
15 return a;
16}
17function sieve(n) {
18 const isPrime = new Array(n + 1).fill(true);
19 isPrime[0] = isPrime[1] = false;
20 for (let i = 2; i * i <= n; i++) {
21 if (!isPrime[i]) continue;
22 for (let j = i * i; j <= n; j += i)
23 isPrime[j] = false;
24 }
25 return isPrime.reduce((acc, p, i) => (p ? acc.concat(i) : acc), []);
26}