Trial division tests primality of n in O(√n). Fine once. Dead if you do it for every value in 1..n at n = 1e6 (∑ √k is not your friend — that is O(n^{3/2})).
The sieve marks multiples of each prime p starting at p*p. Time O(n log log n), memory O(n). CSES Counting Divisors / Sum of Divisors assume you *precompute* something of size n, not that you factor each query from scratch.
Constraint gate: n ≤ 1e7 is a typical sieve. n ≤ 1e12 means you sieve √n and factor one number, or you segment-sieve a range.
function sieve(n) {
const isPrime = Array(n).fill(true);
isPrime[0] = isPrime[1] = false;
for (let p = 2; p * p < n; p++) {
if (!isPrime[p]) continue;
for (let q = p * p; q < n; q += p) isPrime[q] = false;
}
return isPrime;
}
function spfTable(n) {
const spf = Array.from({ length: n }, (_, i) => i);
for (let p = 2; p * p < n; p++) {
if (spf[p] !== p) continue;
for (let q = p * p; q < n; q += p) if (spf[q] === q) spf[q] = p;
}
return spf;
}Checks 0/2