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.749msare 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 and 0 say
true. The loop starts ati = 2, and2 < 1and2 < 0are already false, so the loop body never runs and the function falls through toreturn true. Negatives too:isPrime(-7)is alsotruehere. - 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 <= ninstead ofi <= Math.sqrt(n): whole-number multiplication, no decimals, and no square root recomputed every turn. (i * iis exact in JavaScript for any n up toNumber.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:
- 2 isn't crossed off, so it's prime. Cross off every 2nd number after it: 4, 6, 8, 10...
- 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).
- 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.
- 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 + 1slots so that indexNexists (indexes 0 to N). continueskips 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. Fori > √N,i * i > N, so the inner loop simply doesn't run; thoseiare 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
- 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.)
- 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.
- Why write
i * i <= ninstead ofi <= Math.sqrt(n)? Both work for normal inputs, buti * iis 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. - What is the time complexity of the prime check? O(√n) time, O(1) space. For n ≈ 10⁹, about 31,623 steps.
- 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.
- What is the sieve's complexity? O(n log log n) time, O(n) space.
- 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).
- Why use a
Uint8Arrayfor 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. - What does
^do in JavaScript? Bitwise XOR on the 32-bit integer forms of the operands. Power is**orMath.pow. - 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.
- How do you measure how long code takes in Node.js?
console.time(label)/console.timeEnd(label), orperformance.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 < 2first. - 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 aUint8Array(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.