A prime has exactly two divisors: 1 and itself. The naive test tries every divisor below n, but you only need to go up to √n. If n = a × b with a ≤ b, then a ≤ √n, so any factor pair has one member at most √n.
if (n < 2) return false;
for (let d = 2; d * d <= n; d++) if (n % d === 0) return false;
return true;
That turns O(n) into O(√n), the difference between 10⁹ steps and about 31,623.
Bonus: after checking 2 and 3, every prime is of the form 6k ± 1, which cuts the work roughly by another factor of three.