# Prime sieve in JavaScript

Posted:

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.

```var primes = function() {
var primes = {};

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

primes.create_array = function(n) {
return new Array();
};
}

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

// Simple sieve.
primes.sieve1 = function(n) {
var values = primes.array_init(function(i) { return 1; }, n),
i, j, result;

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

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

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

return primes;
}();
```

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 …