SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 2
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 2 of 30

Number questions II

prime check (why up to √n)all primes up to n (Sieve of Eratosthenes)Armstrong number; loose vs strict loopsperformance with console.time

These are the notes for JavaScript Coding Questions, episode 2, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three more number questions: is n prime?, count every prime up to 10,000,000 and is n an Armstrong number? This time the obvious attempts are not only wrong (0 and 1 come out "prime", 153 comes out "not Armstrong"), some of them are slow, and we measure exactly how slow with console.time.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Plain modern JavaScript, no packages.

About the timings. Lines like sieve: 90.749ms are copied from a real run on one machine. Times vary from machine to machine and from run to run; what matters is the size of the gap (seconds vs milliseconds), not the exact number.

A new tool: console.time and console.timeEnd

console.time(label) starts a stopwatch with a name. console.timeEnd(label) with the same label stops it and prints the label and the time that passed in between.

console.time("loop");
let s = 0;
for (let i = 0; i < 1e6; i++) s += i;
console.timeEnd("loop");
console.timeEnd("nope");
console.log(s);

Output (the warning goes to stderr):

loop: 12.411ms
499999500000
(node:3097) Warning: No such label 'nope' for console.timeEnd()
(Use `node --trace-warnings ...` to show where the warning was created)

A misspelt label does not throw an error; Node only prints a warning and no time. Measure, don't guess.

Q1: Is n a prime number?

Problem. Write isPrime(n) that returns true if the whole number n is prime, otherwise false.

A prime has exactly two divisors: 1 and itself. A divisor of n divides it with remainder 0 (n % i === 0). A whole number greater than 1 that is not prime is composite.

Input Output Why
2 true divisors 1, 2 (the only even prime)
7 true divisors 1, 7
9 false 3 × 3
1 false only one divisor
0 false every number divides 0
25 false 5 × 5, a perfect square
97 true
1000000007 true a huge prime, to test the speed

Think out loud

Input: a whole number. Output: true or false. Plan: try each candidate divisor; if one divides n, it's not prime. Edge cases: 0, 1 and negatives (not prime by definition), 2 (the smallest prime), a perfect square like 25 (the divisor is exactly the square root), and a huge prime (the loop has to run all the way, so it's the slowest case).

The obvious attempt

Try every number from 2 up to n - 1.

function isPrime(n) {
  for (let i = 2; i < n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}
for (const n of [2, 7, 9, 1, 0]) console.log(n, isPrime(n));
console.time("1000000007");
console.log(isPrime(1000000007));
console.timeEnd("1000000007");

Output:

2 true
7 true
9 false
1 true
0 true
true
1000000007: 2.038s

Two bugs:

  1. 1 and 0 say true. The loop starts at i = 2, and 2 < 1 and 2 < 0 are already false, so the loop body never runs and the function falls through to return true. Negatives too: isPrime(-7) is also true here.
  2. One number took about two seconds. For a prime, no divisor is ever found, so the loop runs all the way: about a billion % operations. This is trial division done the slow way.

Why √n is enough: divisors come in pairs

Arrange 36 chairs in equal rows: 1 row of 36, 2 rows of 18, 3 of 12, 4 of 9, 6 of 6. Every divisor a has a partner b = n / a with a × b = n.

const n = 36;
for (let i = 1; i * i <= n; i++) if (n % i === 0) console.log(i, "x", n / i);
1 x 36
2 x 18
3 x 12
4 x 9
6 x 6

In the middle is 6 × 6: the square root, √36 = 6. In every pair one number is at most √n and the other at least √n (if both were bigger than √n, their product would be bigger than n). After 6 you only meet the same pairs turned around: 9 rows of 4 is 4 rows of 9. So if nothing from 2 to √n divides n, nothing above √n can either. Stop as soon as i * i > n.

For n = 1,000,000,007 that's about 31,623 checks instead of a billion:

console.log(Math.sqrt(1000000007));
31622.77671236351

The fix

function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}
for (const n of [2, 7, 9, 1, 0, 25, 97]) console.log(n, isPrime(n));
console.time("1000000007");
console.log(isPrime(1000000007));
console.timeEnd("1000000007");

Output:

2 true
7 true
9 false
1 false
0 false
25 false
97 true
true
1000000007: 0.772ms
  • if (n < 2) return false; handles 0, 1 and every negative number.
  • i * i <= n instead of i <= Math.sqrt(n): whole-number multiplication, no decimals, and no square root recomputed every turn. (i * i is exact in JavaScript for any n up to Number.MAX_SAFE_INTEGER.)
  • 25 is caught because the loop includes i * i === n (<=, not <).

From about 2 seconds to under a millisecond, for the same answer.

Follow-up: skip the even numbers

Interviewers often ask: "can you make it twice as fast?" After checking 2, every other even divisor is pointless: if n is not divisible by 2, it cannot be divisible by 4, 6 or 8 either. So handle even numbers once, then try only odd divisors.

function isPrime(n) {
  if (n < 2) return false;
  if (n % 2 === 0) return n === 2;
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}
for (const n of [2, 4, 9, 1, 25, 97]) console.log(n, isPrime(n));
console.log(isPrime(1000000007), isPrime(1000000008));

Output:

2 true
4 false
9 false
1 false
25 false
97 true
true false

Still O(√n), but about half the divisions. Mention it as a small improvement after the big one (stopping at √n).

Complexity

The loop runs at most √n times. Time O(√n), space O(1) (a couple of variables, whatever n is).

Q2: Count all the primes up to N

Problem. Count the primes ≤ N for N = 10,000,000.

Input Output
N = 30 10 primes: 2 3 5 7 11 13 17 19 23 29
N = 10000000 664579 primes

Think out loud

We already have a fast isPrime, so the obvious plan is to call it on every number from 2 to N. Edge cases: N < 2 (no primes), and the size: ten million numbers, in an online test that may have a one-second limit.

The obvious attempt: isPrime on every number

function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}
const N = 10000000;
console.time("one by one");
let count = 0;
for (let n = 2; n <= N; n++) if (isPrime(n)) count++;
console.log(count, "primes");
console.timeEnd("one by one");

Output:

664579 primes
one by one: 3.361s

The right count, but more than three seconds: a fail with a one-second limit.

Why? Each number does its own trial divisions, up to its own square root, and all that work is thrown away before the next number. Ten million numbers, each checked from scratch; for the primes (the slowest case) that's up to √n divisions each. Roughly O(N √N) in the worst case.

The Sieve of Eratosthenes

Over 2,000 years old, from the Greek mathematician Eratosthenes. Picture a teacher with a register of roll numbers 2 to 30, none marked:

  1. 2 isn't crossed off, so it's prime. Cross off every 2nd number after it: 4, 6, 8, 10...
  2. The next unmarked number, 3, is prime. Cross off its multiples starting at 3 × 3 = 9: 9, 12, 15... (6 was already crossed off by 2).
  3. The next unmarked is 5: start at 25. Every smaller multiple of 5 (10, 15, 20) already has a smaller prime factor and is already crossed off.
  4. Whatever is never crossed off is prime. No division at all.

In code we keep one flag per number in a Uint8Array: a typed array of fixed length whose items are whole numbers from 0 to 255, one byte each, all starting at 0. isComposite[i] = 1 means "crossed off".

function sieve(N) {
  const isComposite = new Uint8Array(N + 1);
  const primes = [];
  for (let i = 2; i <= N; i++) {
    if (isComposite[i]) continue;
    primes.push(i);
    for (let j = i * i; j <= N; j += i) isComposite[j] = 1;
  }
  return primes;
}
console.log(sieve(30).join(" "));
console.time("sieve");
console.log(sieve(10000000).length, "primes");
console.timeEnd("sieve");

Output:

2 3 5 7 11 13 17 19 23 29
664579 primes
sieve: 90.749ms

The same ten primes up to 30 and the same 664579 up to ten million, in under a tenth of a second instead of more than three seconds.

  • The array has N + 1 slots so that index N exists (indexes 0 to N).
  • continue skips a crossed-off number: it's composite, and its multiples were already crossed off by its smallest prime factor.
  • The inner loop starts at i * i. For i > √N, i * i > N, so the inner loop simply doesn't run; those i are only being collected.

Complexity

Each prime p crosses off about N / p numbers. Adding N/2 + N/3 + N/5 + N/7 + ... over all primes up to N gives about N log log N. log log N grows extremely slowly (for N = 10,000,000, ln N ≈ 16.1 and ln 16.1 ≈ 2.8), so the sieve is almost linear.

Time O(n log log n), space O(n): one byte per number, 10,000,001 bytes, about 9.5 MB here. We traded memory for speed, a trade you'll make again and again.

Q3: Armstrong number

Problem. Let k be the number of digits of n. Raise every digit to the power k and add them up. If the sum equals n, n is an Armstrong number (also called a narcissistic number). Write isArmstrong(n).

Input Working Output
153 3 digits: 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 true
370 3³ + 7³ + 0³ = 27 + 343 + 0 = 370 true
9474 4 digits: 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 true
123 1 + 8 + 27 = 36 false
7 1 digit: 7¹ = 7 true
0 0¹ = 0 true
10 1² + 0² = 1 false

Think out loud

Input: a whole number. Output: true/false. Get the digits (easiest: String(n) and loop over its characters, Number(ch) turns "5" into 5), raise each to a power and add. Edge cases: one-digit numbers (always true), 0, negative numbers (the - is not a digit: treat them as not Armstrong), and numbers with 4 or more digits.

The obvious attempt: ^ for power

Many people write power with the caret, like on a calculator:

function isArmstrong(n) {
  let sum = 0;
  for (const ch of String(n)) sum += Number(ch) ^ 3;
  return sum === n;
}
for (const n of [153, 370, 9474, 123]) console.log(n, isArmstrong(n));

Output:

153 false
370 false
9474 false
123 false

False for everything, even 153, with no error.

Why? In JavaScript ^ is bitwise XOR, not power. XOR compares the binary bits of two numbers and gives 1 where they differ:

for (const d of [1, 5, 3]) console.log(d, "^ 3 =", d ^ 3, "  ", d, "** 3 =", d ** 3);
console.log((1).toString(2).padStart(3, "0"), "^", (3).toString(2).padStart(3, "0"), "=", (1 ^ 3).toString(2).padStart(3, "0"));
console.log((5).toString(2), "^", (3).toString(2).padStart(3, "0"), "=", (5 ^ 3).toString(2));
1 ^ 3 = 2    1 ** 3 = 1
5 ^ 3 = 6    5 ** 3 = 125
3 ^ 3 = 0    3 ** 3 = 27
001 ^ 011 = 010
101 ^ 011 = 110

So for 153 the sum was 2 + 6 + 0 = 8, not 153. Power in JavaScript is the exponent operator ** (or Math.pow(a, b)).

Second attempt: ** 3

function isArmstrong(n) {
  let sum = 0;
  for (const ch of String(n)) sum += Number(ch) ** 3;
  return sum === n;
}
for (const n of [153, 370, 9474, 123]) console.log(n, isArmstrong(n));

Output:

153 true
370 true
9474 false
123 false

153 and 370 are fixed, but 9474 is still false. We hard-coded the power 3; 9474 has four digits, so it needs the power 4 (with cubes it gives 729 + 64 + 343 + 64 = 1200). The power is the number of digits, which depends on the input. Never hard-code what the problem says depends on the input.

The fix

function isArmstrong(n) {
  if (n < 0) return false;
  const digits = String(n);
  const k = digits.length;
  let sum = 0;
  for (const ch of digits) sum += Number(ch) ** k;
  return sum === n;
}
for (const n of [153, 370, 9474, 123, 7, 0, 10]) console.log(n, isArmstrong(n));
const all = [];
for (let n = 1; n <= 100000; n++) if (isArmstrong(n)) all.push(n);
console.log(all.join(" "));

Output:

153 true
370 true
9474 true
123 false
7 true
0 true
10 false
1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084

All seven test cases right: a single digit to the power 1 is itself, so 0 to 9 are Armstrong numbers. And every Armstrong number up to 100,000: 1 to 9, then 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084. (There are no two-digit ones.)

Complexity

One step per digit. With d = the number of digits of n (about log₁₀ n), time O(d) for one number and space O(d) for the digits string. With the % 10 / Math.trunc(n / 10) digit loop from episode 1 you can avoid the string for O(1) space (count the digits first, then loop again).

Complexity summary

Question Approach Time Extra space Real run
Prime check try every i < n O(n) O(1) 2.038s for 1000000007
Prime check try i while i * i <= n O(√n) O(1) 0.772ms
Primes up to N isPrime on every number about O(N √N) O(1) 3.361s for N = 10⁷
Primes up to N Sieve of Eratosthenes, Uint8Array O(n log log n) O(n) 90.749ms
Armstrong power = number of digits O(d) O(d)

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
No check for n < 2 for (let i = 2; i < n; i++) ...; return true; isPrime(1), isPrime(0), isPrime(-7) → true true true the loop never runs if (n < 2) return false;
Trying every divisor up to n i < n 1000000007: 2.038s a billion divisions; divisors pair up around √n i * i <= n
< instead of <= with √n i * i < n isPrime(25) → true misses the divisor exactly at √n i * i <= n
isPrime on 10 million numbers for (n = 2; n <= N; n++) if (isPrime(n)) one by one: 3.361s each number starts from scratch the sieve
Sieve array one slot too short new Uint8Array(N) index N is out of range: reading it gives undefined, writing does nothing, no error indexes go 0 to N - 1 new Uint8Array(N + 1)
Storing a big number in a Uint8Array u[1] = 256 Uint8Array(3) [ 1, 0, 1 ] values wrap modulo 256 store only 0/1 flags
^ for power Number(ch) ^ 3 153 false ^ is bitwise XOR Number(ch) ** 3
Hard-coded power 3 ** 3 9474 false the power is the digit count ** String(n).length
Minus before ** -2 ** 2 SyntaxError: Unary operator used immediately before exponentiation expression. Parenthesis must be used to disambiguate operator precedence ambiguous: -(2²) or (-2)²? (-2) ** 2 → 4, or -(2 ** 2)
Mismatched timer label console.timeEnd("nope") Warning: No such label 'nope' for console.timeEnd() the label must match console.time exactly copy the same string

The i * i < n and new Uint8Array(N) rows, checked for real:

function isPrimeLt(n) {
  if (n < 2) return false;
  for (let i = 2; i * i < n; i++) if (n % i === 0) return false;
  return true;
}
console.log(isPrimeLt(7), isPrimeLt(25), isPrimeLt(97));
const N = 10;
const short = new Uint8Array(N);
short[N] = 1;
console.log(short[N], short.length);
true true true
undefined 10

With <, 25 never tests i = 5, so it comes out "prime"; and the write to index N past the end of the typed array is silently ignored.

Mini project: a number inspector

Give it some numbers on the command line and it says what each one is: its prime factors, and whether it's prime, Armstrong or perfect (see the practice questions). It reuses every function from today.

// Number inspector: node main.js 153 97 28 9474
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
  return true;
}
function primeFactors(n) {
  const f = [];
  for (let p = 2; p * p <= n; p++) {
    while (n % p === 0) { f.push(p); n /= p; }
  }
  if (n > 1) f.push(n);
  return f;
}
function isArmstrong(n) {
  if (n < 0) return false;
  const digits = String(n);
  let sum = 0;
  for (const ch of digits) sum += Number(ch) ** digits.length;
  return sum === n;
}
function isPerfect(n) {
  if (n < 2) return false;
  let sum = 1;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) { sum += i; if (n / i !== i) sum += n / i; }
  }
  return sum === n;
}

const inputs = process.argv.length > 2 ? process.argv.slice(2) : ["153", "97", "28", "9474", "1", "abc"];
for (const text of inputs) {
  const n = Number(text);
  if (!Number.isSafeInteger(n) || n < 0) {
    console.log(`${text}: not a whole number >= 0, skipped`);
    continue;
  }
  const tags = [];
  if (isPrime(n)) tags.push("prime");
  if (isArmstrong(n)) tags.push("Armstrong");
  if (isPerfect(n)) tags.push("perfect");
  const f = n >= 2 ? primeFactors(n).join(" x ") : "-";
  console.log(`${n}: factors ${f} | ${tags.length ? tags.join(", ") : "nothing special"}`);
}

node main.js (the default list):

153: factors 3 x 3 x 17 | Armstrong
97: factors 97 | prime
28: factors 2 x 2 x 7 | perfect
9474: factors 2 x 3 x 1579 | Armstrong
1: factors - | Armstrong
abc: not a whole number >= 0, skipped

node main.js 1000000007 370 8128 -5:

1000000007: factors 1000000007 | prime
370: factors 2 x 5 x 37 | Armstrong
8128: factors 2 x 2 x 2 x 2 x 2 x 2 x 127 | perfect
-5: not a whole number >= 0, skipped

Number.isSafeInteger rejects text that isn't a number (Number("abc") is NaN), decimals, and numbers too big to be exact. Extend it: add "even/odd", or the number of primes up to n using the sieve.

Your turn: count the primes in a range [a, b] (solution)

Problem. Count the primes between a and b, both included. a = 10, b = 30 → 6 (11 13 17 19 23 29).

Hint from the video: sieve once up to b, then count from a. What if a < 2?

The trap. If you sieve but forget that 0 and 1 are not prime, they are never crossed off (no prime has them as a multiple), so they get counted:

function countPrimesInRange(a, b) {
  const isComposite = new Uint8Array(b + 1);
  for (let i = 2; i * i <= b; i++) {
    if (isComposite[i]) continue;
    for (let j = i * i; j <= b; j += i) isComposite[j] = 1;
  }
  let count = 0;
  for (let n = a; n <= b; n++) if (!isComposite[n]) count++;
  return count;
}
console.log(countPrimesInRange(10, 30));
console.log(countPrimesInRange(0, 10));
6
6

[0, 10] should be 4 (2 3 5 7), but 0 and 1 were counted too.

Show the solution

Mark 0 and 1 as not prime and start counting at Math.max(a, 2). Return 0 for an empty range (a > b) or when b < 2. Since we only need a count here, the outer loop can stop at i * i <= b (every composite up to b has a prime factor ≤ √b).

function countPrimesInRange(a, b) {
  if (b < 2 || a > b) return 0;
  const isComposite = new Uint8Array(b + 1);
  isComposite[0] = 1;
  isComposite[1] = 1;
  for (let i = 2; i * i <= b; i++) {
    if (isComposite[i]) continue;
    for (let j = i * i; j <= b; j += i) isComposite[j] = 1;
  }
  let count = 0;
  for (let n = Math.max(a, 2); n <= b; n++) if (!isComposite[n]) count++;
  return count;
}
const tests = [[10, 30], [0, 10], [1, 2], [2, 2], [14, 16], [0, 1], [30, 10], [1, 10000000]];
for (const [a, b] of tests) console.log(`[${a}, ${b}] ->`, countPrimesInRange(a, b));

Output:

[10, 30] -> 6
[0, 10] -> 4
[1, 2] -> 1
[2, 2] -> 1
[14, 16] -> 0
[0, 1] -> 0
[30, 10] -> 0
[1, 10000000] -> 664579

Time O(b log log b), space O(b). If you have to answer many ranges, build a prefix count once (pc[i] = number of primes ≤ i) and answer each range as pc[b] - pc[a - 1] in O(1).

Practice questions (with solutions)

1. Print the prime factors of n (60 → 2 2 3 5).

Solution

Divide out each p while it divides n, starting from 2. Only primes ever divide (by the time p = 4, all the 2s are gone). Stop at p * p <= n; whatever is left above 1 is one last prime factor.

function primeFactors(n) {
  const factors = [];
  for (let p = 2; p * p <= n; p++) {
    while (n % p === 0) {
      factors.push(p);
      n = n / p;
    }
  }
  if (n > 1) factors.push(n);
  return factors;
}
for (const n of [60, 97, 1, 2, 1024, 360, 1000000007, 999999999989 * 1]) console.log(n, "->", primeFactors(n).join(" "));

Output:

60 -> 2 2 3 5
97 -> 97
1 -> 
2 -> 2
1024 -> 2 2 2 2 2 2 2 2 2 2
360 -> 2 2 2 3 3 5
1000000007 -> 1000000007
999999999989 -> 999999999989

1 has no prime factors (an empty list). Time O(√n) in the worst case (n prime), space O(log n) for the list (at most log₂ n factors).

2. Is n a perfect number? A perfect number equals the sum of its divisors other than itself: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14.

Solution

Use the pairs idea from Q1: each divisor i ≤ √n brings its partner n / i. Two traps, both visible in this first try:

function isPerfect(n) {
  let sum = 0;
  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) sum += i + n / i;
  }
  return sum === n;
}
for (const n of [6, 28, 36, 1]) console.log(n, isPerfect(n));
6 false
28 false
36 false
1 false

At i = 1 the partner is n itself, which must not be counted (so the sum is 2n for 6 and 28), and for a square like 36 the divisor 6 would be added twice. The fix: start the sum at 1, loop from 2, and add the partner only when it's different.

function isPerfect(n) {
  if (n < 2) return false;
  let sum = 1;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      sum += i;
      const partner = n / i;
      if (partner !== i) sum += partner;
    }
  }
  return sum === n;
}
for (const n of [6, 28, 12, 1, 0, 496, 8128, 36]) console.log(n, isPerfect(n));
const all = [];
for (let n = 1; n <= 100000; n++) if (isPerfect(n)) all.push(n);
console.log(all.join(" "));

Output:

6 true
28 true
12 false
1 false
0 false
496 true
8128 true
36 false
6 28 496 8128

1 is not perfect (its only divisor is itself, so the sum of the others is 0). Time O(√n), space O(1).

3. The sieve with a normal Array instead of a Uint8Array: compare the time.

Solution
function sieveArray(N) {
  const isComposite = new Array(N + 1).fill(false);
  let count = 0;
  for (let i = 2; i <= N; i++) {
    if (isComposite[i]) continue;
    count++;
    for (let j = i * i; j <= N; j += i) isComposite[j] = true;
  }
  return count;
}
function sieveTyped(N) {
  const isComposite = new Uint8Array(N + 1);
  let count = 0;
  for (let i = 2; i <= N; i++) {
    if (isComposite[i]) continue;
    count++;
    for (let j = i * i; j <= N; j += i) isComposite[j] = 1;
  }
  return count;
}
const N = 10000000;
console.time("Array");
console.log(sieveArray(N), "primes");
console.timeEnd("Array");
console.time("Uint8Array");
console.log(sieveTyped(N), "primes");
console.timeEnd("Uint8Array");
const a = new Uint8Array(N + 1);
console.log(a.byteLength, "bytes");

Output (times vary by machine):

664579 primes
Array: 159.004ms
664579 primes
Uint8Array: 67.331ms
10000001 bytes

And the memory, measured with process.memoryUsage():

const N = 10000000;
const mb = (x) => (x / 1024 / 1024).toFixed(1) + " MB";
let before = process.memoryUsage();
const arr = new Array(N + 1).fill(false);
let after = process.memoryUsage();
console.log("Array of booleans: heapUsed +", mb(after.heapUsed - before.heapUsed));
before = process.memoryUsage();
const typed = new Uint8Array(N + 1);
after = process.memoryUsage();
console.log("Uint8Array:        arrayBuffers +", mb(after.arrayBuffers - before.arrayBuffers));
console.log(arr.length, typed.length);
Array of booleans: heapUsed + 76.3 MB
Uint8Array:        arrayBuffers + 9.5 MB
10000001 10000001

A filled normal array is still the same algorithm, so it's only a little slower here, but it uses about 8 times the memory (each slot holds an 8-byte reference to true/false; a Uint8Array slot is 1 byte). Starting from an empty [] and growing it with holes is worse:

function sieveArray(N) {
  const isComposite = [];
  let count = 0;
  for (let i = 2; i <= N; i++) {
    if (isComposite[i]) continue;
    count++;
    for (let j = i * i; j <= N; j += i) isComposite[j] = true;
  }
  return count;
}
console.time("empty []");
console.log(sieveArray(10000000), "primes");
console.timeEnd("empty []");
664579 primes
empty []: 313.898ms

Writing to index 4, then 6, then 8 of an empty array leaves holes, so the engine stores it in a slower layout. A typed array has a fixed size, one number type, and no holes.

Quick quiz

1. (From the video.) What does this print?

console.log(2 ^ 3, 2 ** 3);

(A) 8 8 (B) 1 8 (C) 6 9 (D) 8 1

Answer

(B) 1 8. 2 ^ 3 is bitwise XOR: 2 is 10 in binary and 3 is 11; they differ only in the last bit, so the result is 01, which is 1. 2 ** 3 is power: 2 × 2 × 2 = 8. (Real output: 1 8.)

2. What does console.log(2 ** 3 ** 2) print? (A) 64 (B) 512 (C) 36

Answer

(B) 512. ** groups from the right: 2 ** (3 ** 2) = 2⁹ = 512.

3. What does this print?

const u = new Uint8Array(3);
u[0] = 1; u[1] = 256; u[2] = true;
console.log(u);
Answer
Uint8Array(3) [ 1, 0, 1 ]

A Uint8Array holds only 0 to 255: 256 wraps around to 0, and true is converted to the number 1.

4. The loop condition i * i <= n is changed to i * i < n. Which input now gives the wrong answer: 7, 25 or 97?

Answer

25. Its only divisor besides 1 and 25 is 5, and 5 * 5 < 25 is false, so 5 is never tried and 25 comes out "prime". Every perfect square of a prime (4, 9, 49...) breaks the same way.

Interview questions

  1. Why is 1 not a prime number? A prime has exactly two different divisors; 1 has only one. (It also keeps "every number has exactly one prime factorisation" true.)
  2. Why is it enough to check divisors up to √n? Divisors come in pairs a × b = n; if both were greater than √n their product would exceed n, so one of each pair is ≤ √n. If none up to √n divides n, none above it does.
  3. Why write i * i <= n instead of i <= Math.sqrt(n)? Both work for normal inputs, but i * i is exact whole-number arithmetic, avoids a floating-point square root (which can round just below the true value for very large perfect squares) and doesn't recompute it every turn.
  4. What is the time complexity of the prime check? O(√n) time, O(1) space. For n ≈ 10⁹, about 31,623 steps.
  5. How does the Sieve of Eratosthenes work, and why start crossing off at i × i? Keep a flag per number; for each unmarked i (a prime), mark its multiples. Multiples smaller than i × i have a smaller prime factor and are already marked.
  6. What is the sieve's complexity? O(n log log n) time, O(n) space.
  7. When is the sieve better than calling isPrime many times, and when not? Better when you need many primes up to a known limit (all primes ≤ n, many queries). Worse for one huge number like 10¹² (you can't allocate 10¹² bytes; √n trial division takes 10⁶ steps).
  8. Why use a Uint8Array for the sieve? One byte per flag, fixed size, no holes, all zeros at the start: about 10 MB for 10 million flags vs about 76 MB for a normal array of booleans here, and faster.
  9. What does ^ do in JavaScript? Bitwise XOR on the 32-bit integer forms of the operands. Power is ** or Math.pow.
  10. What is an Armstrong number, and what's the common bug? A number equal to the sum of its digits each raised to the number of digits (153, 9474). The bug is hard-coding the power 3.
  11. How do you measure how long code takes in Node.js? console.time(label) / console.timeEnd(label), or performance.now() before and after.

Glossary

Term Meaning Example
Prime number A whole number greater than 1 with exactly two divisors: 1 and itself 2, 7, 97, 1000000007
Divisor A number that divides n with remainder 0 3 is a divisor of 9: 9 % 3 === 0
Composite number A whole number greater than 1 that is not prime 9 = 3 × 3, 25
Divisor pair Two divisors whose product is n 4 × 9 = 36
Square root (√n) The number that multiplied by itself gives n √36 = 6, Math.sqrt(36)
Perfect square A number that is some whole number times itself 25 = 5 × 5
Trial division Testing primality by trying divisors one by one for (i = 2; i * i <= n; i++)
% (remainder operator) The remainder after division 10 % 3 is 1
console.time / console.timeEnd Start / stop a named stopwatch and print the time between them sieve: 90.749ms
Sieve of Eratosthenes Finds all primes up to N by crossing off the multiples of each prime crossing off 4, 6, 8... then 9, 12, 15...
Multiple n times a whole number 12 is a multiple of 3
Prime factor A prime that divides n 60 = 2 × 2 × 3 × 5
Typed array A fixed-length array whose items all have one numeric type, stored compactly Uint8Array, Int32Array, Float64Array
Uint8Array A typed array of unsigned 8-bit integers (0 to 255), one byte each, starting at 0 new Uint8Array(N + 1)
Byte 8 bits; holds 0 to 255 one Uint8Array slot
Flag A value that just means yes or no isComposite[j] = 1
continue Skip the rest of this loop turn and go to the next one skip a crossed-off number
Binary Writing numbers with only the digits 0 and 1 5 is 101
Bitwise XOR (^) Compares bits; 1 where the two bits differ 5 ^ 3 is 6 (101 ^ 011 = 110)
Exponent operator (**) Raises a number to a power; groups from the right 5 ** 3 is 125, 2 ** 3 ** 2 is 512
Math.pow(a, b) The function form of a ** b Math.pow(2, 10) is 1024
Armstrong number Equals the sum of its digits, each raised to the number of digits 153, 9474
Perfect number Equals the sum of its divisors other than itself 6, 28, 496, 8128
Number.isSafeInteger True for whole numbers JavaScript can store exactly (up to 2⁵³ - 1) Number.isSafeInteger(2.5) is false
Edge case An input at the boundary that often breaks code 0, 1, 25, a huge prime
Time complexity How the number of steps grows as the input grows O(√n)
Space complexity How the extra memory grows as the input grows O(n) for the sieve
Big-O notation The growth rate, ignoring constant factors O(n), O(√n)
O(√n) Steps grow like the square root of n 31,623 steps for 10⁹
O(1) A fixed amount, whatever the input a few variables
O(d) Grows with the number of digits d of n (about log₁₀ n) Armstrong check
log log n The logarithm of the logarithm of n; grows extremely slowly ln ln 10⁷ ≈ 2.8
O(n log log n) Almost linear: a little more than n steps the sieve
Memory/speed trade-off Using more memory to save time (or the other way round) the sieve's 10 MB of flags

Summary

  • 0, 1 and negative numbers are not prime: check n < 2 first.
  • Divisors come in pairs around √n: test only while i * i <= n. O(√n) time, O(1) space: 2 seconds became under a millisecond.
  • console.time(label) / console.timeEnd(label) measure code; the labels must match.
  • For all primes up to N, sieve: cross off multiples starting at i * i, in a Uint8Array(N + 1). O(n log log n) time, O(n) space: 3.4 seconds became under 0.1 seconds.
  • ^ is bitwise XOR; ** is power.
  • An Armstrong number uses the number of digits as the power, not always 3. O(d) time.
  • Always test 0, 1, a perfect square and a huge input.

Next episode: Number questions III: GCD and LCM with Euclid's trick, a factorial too big for a normal number (BigInt), and Fibonacci three ways.