Prime sieve in JavaScript

Update : After running the C version through Emscripten, the result is about the same speed as the C version when run through Firefox. Wow!

Update : Switching from a Javascript `Array` to `Int8Array` halved the time in Firefox, making it comparable to C and Emscripten. (Until moving C to 8 bits, then things got faster there as well …).

Ok, time for some more prime sieving. This time, we are going to try JavaScript, Python, and C.

First, the Python code

```import numpy as np

def sieve1(n):
values = np.arange(n)
values[1] = 0
# values[4::2] = 0
for i in xrange(n):
i2 = i*i
if i2 >= n:
break
if values[i]:
values[i2::i] = 0
result = values[values > 0]
return result
```

This is the normal sieve. The inner loop is in NumPy, and running

`%timeit ps = primes_np.sieve1(15485864)`

Gives me a list of first million primes in about 425 ms on my laptop.

Next, C.

```#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
const int n = 15485864;
clock_t start = clock();
int *arr = malloc(n * sizeof(int));

for(int i = 0; i < n; ++i) { arr[i] = i; }
arr[1] = 0;

for(int i = 0; i < n; ++i) {
int d = i * i;
if(d >= n) { break; }
if(arr[i]) {
for(int j = d; j < n; j += i) {
arr[j] = 0;
}
}
}
int count = 0;
for(int i = 0; i < n; ++i) {
if(arr[i]) { ++count; }
}
clock_t end = clock();
printf("found %d primes less than %d\n", count, n);
double duration = (end - start) / (double)CLOCKS_PER_SEC;
printf("took %f seconds\n", duration);
}
```

This code took about 280 ms. (`clang -O3`)

Finally, the JavaScript version.

```const create_array = (() => {
// Create an array of values as the result of calling fcn[i] for 0
// <= i < n
if(typeof Int8Array === 'function') {
return (n) => {
return new Int8Array(n);
};
} else {
return () => {
return new Array();
};
}
})();

const array_init = function(fcn, n) {
const result = create_array(n);
for(let i = 0; i < n; i++) {
result[i] = fcn(i);
}
return result;
};

// Simple sieve.
const sieve1 = function(n) {
const values = array_init(() => 1, n);

values[1] = 0;
values[0] = 0;

for(let i = 0; i < n; i++) {
if(values[i] > 0) {
if(i*i > n) { break; }
for(let j = i*i; j < n; j += i) {
values[j] = 0;
}
}
}

const result = [];
for(let j = 0; j < values.length; j += 1) {
if(values[j] > 0) {
result.push(j);
}
}
return result;
};

export {sieve1};
```

This takes around 650 ms on the same computer.

None of these examples were tweaked or tested rigorously …

Just for fun, you can run the JavaScript on this page. The millionth prime should be 15,485,863.

See the results here …