Multi tool use

Clash Royale CLAN TAG

How do I calculate all prime numbers with a really large max in the browser using JSFiddle

I am working on some of the typical katas for JS and I came across one that wanted all the primes for a really large number. I tried the following in JSFiddle.

findPrimes(max){
let dont = , primes = ;
for (var i = 2; i <= max; i++) {
if (!dont[i]) {
primes.push(i);
for (var j = i; j <= max; j += i) dont[j] = true;
}
}
}


This works relatively good till about this.findPrimes(51475143);, however, if I try say... this.findPrimes(851475143); I get a sad face an the JS engine appears to crash. I know I could probably do straight V8 and squeeze a bit out and maybe even go toward a C-based node module but to keep things simple I would like to keep it in the browser if possible. If not and proof can be provided I will accept that answer.

this.findPrimes(51475143);

this.findPrimes(851475143);

1 Answer
1

The problem you're having is likely due to running out of memory, with your dont array being the culprit. Luckily, since it's just an array of booleans, you can do the same thing with a bit array, which will save some space.

dont

JavaScript doesn't have any native bit array type, but you can simulate one by storing an array of 32-bit numbers and using bitwise operators to retrieve or set the desired bit. So something like:

class BitArray {
constructor(len) {
this.arr = Array(Math.ceil(len / 32)).fill(0)
}

set(i) {
const j = Math.floor(i / 32)
this.arr[j] = this.arr[j] | (1 << (i % 32))
}

get(i) {
const j = Math.floor(i / 32)
return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
}
}


Then, with that alone, you can run your snippet and get a result (although it takes a while):

class BitArray {
constructor(len) {
this.arr = Array(Math.ceil(len / 32)).fill(0)
}

set(i) {
const j = Math.floor(i / 32)
this.arr[j] = this.arr[j] | (1 << (i % 32))
}

get(i) {
const j = Math.floor(i / 32)
return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
}
}

function findPrimes(max) {
const dont = new BitArray(max)
const primes = ;
for (var i = 2; i <= max; i++) {
if (!dont.get(i)) {
primes.push(i);
for (var j = i * 2; j <= max; j += i) dont.set(j);
}
}

return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

However, in addition to that, you can do a few more optimizations to your sieve:

j

i*i

i

i

dont

i += 2

i++

i*2

i

j + i*(odd)

Using those, you can change your snippet to:

class BitArray {
constructor(len) {
this.arr = Array(Math.ceil(len / 32)).fill(0)
}

set(i) {
const j = Math.floor(i / 32)
this.arr[j] = this.arr[j] | (1 << (i % 32))
}

get(i) {
const j = Math.floor(i / 32)
return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
}
}

function findPrimes(max) {
const dont = new BitArray(max / 2) // Only need half the memory, since we only check odds.
const primes = [2]; // We already know 2 is prime
for (var i = 3; i <= max; i += 2) { // Start at 3, increment by 2, so only odds are checked.
if (!dont.get((i-1)/2)) { // The (i-1)/2 converts each odd to it's "halfway" number
primes.push(i);
for (var j = i*i; j <= max; j += i*2) dont.set((j-1)/2);
}
}

return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

As you can see, you get the same result for the last 10 primes, and, at least anecdotally, it seems to run quite a bit faster.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.