primesieve

A compact (bitfield) prime sieve in JavaScript together with all the functions to use it

Author(s)

Christoph Zurnieden [e-mail]

Installation

$ git clone https://github.com/czurnieden/primesieve.git
$ cd primesieve
$ npm install -g

There is also a Unix (or newer Macs) dependent CLI version in ./bin which gets not installed by default, yet and might be behind the current version.

Version

0.2.1 Bugfix: replaced wheel for wheel factorization and corrected factorization code
0.2.0 Added prime factoring and testing up to 2⁵³ and JDOC-3 documentation
0.1.0 Corrected error in fallback to normal Array
0.0.3 Corrected error in GIT url
0.0.2 Additional function to get the raw prime sieve.
0.0.1 Initial publication

Description

This library implements a prime sieve with a bitfield in an UInt32Array (or a normal Array if UInt32Array is not available). That means that the memory used is about the size of the biggest prime evaluated. E.g.: if the highest prime evaluated is 7927 the memory used is about ceil(7927/32)*8 = 1984 bytes large.

That is only an approximation because ECMAScript offers no direct memory control.

The largest prime available would be at least 2147483647 on a 32-bit systems and a wee bit more on 64-bit systems but no guarantee for the latter.

Please be aware that that sieve would be 2 gigabytes large.

Further optimizations can be done by ignoring all even numbers (except the even primes), maybe all multiples of 3, too. If you need such large sieves regularly and in JavaScript: feel free to ask the author.

Usage

The usage is like with any other node/browser module:

var sieve = require('primesieve');
var array_of_first_five_primes = sieve.primes(5);

Documentation

The documentation is in the ./docs directory now, autogenerated by JSDOC version 3.

Example

With node.js

var p = require('primesieve');
function primorial(n,result){
  var primes, ret, primepi;
 
  // checks of arguments omitted for brevity
 
  primepi = p.primePi(n);
  if(typeof primepi === 'undefined'){
    return p.strerror();
  }
 
  primes = p.primes(primepi);
  if(typeof primes === 'undefined'){
    return p.strerror();
  }
 
  ret = 1;
  for(var i = 0; i < primepi; i++){
    ret *= primes[i];
  }
  result[0] = ret;
  return p.strerror();
}

With a browser (tested in Firefox 33.0.0)

// the module must be included somewhere or just put on top
var p = primesieve;
 
function primorial(n,result){
  var primes, ret, primepi;
 
  // checks of arguments omitted for brevity
 
  primepi = p.primePi(n);
  if(typeof primepi === 'undefined'){
    return p.strerror();
  }
 
  primes = p.primes(primepi);
  if(typeof primes === 'undefined'){
    return p.strerror();
  }
 
  ret = 1;
  for(var i = 0; i < primepi; i++){
    ret *= primes[i];
  }
  result[0] = ret;
  return p.strerror();
}

In a much simpler but frowned upon way:

var primorial = eval(p.primes(8).join("*"));

Yes, eval is not the devil; it has its uses, although not here.

Test

A test with a vows script is implemented. Please run if vows is installed:

npm test

Or, if that doesn't work:

node primesieve-test.js

If it still doesn't work with an error raised for not finding vows despite being installed--install vows again, this time locally, that is, without the -g option. The npm packet manager is a bit peculiar in this regard.