Skip to content

Instantly share code, notes, and snippets.

@alanthird
Last active August 29, 2015 14:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alanthird/169e4942c2016909d0b5 to your computer and use it in GitHub Desktop.
Save alanthird/169e4942c2016909d0b5 to your computer and use it in GitHub Desktop.
Javascript stream-based prime number checking
function millerRabin(n) {
function isOdd(n) {
return n%2===1;
}
function rnd(floor, ceil) {
return floor+Math.floor(Math.random()*(ceil-floor));
}
function expmod(base, exponent, mod) {
var result=1;
while (exponent > 0) {
if (isOdd(exponent)) {
result=result*base%mod;
exponent--;
}
base=base*base%mod;
exponent=exponent/2;
}
return result;
}
function test(q, s) {
var a=rnd(1, n-1);
var apowq=expmod(a, q, n);
if (apowq===1 || apowq===n-1) return true;
console.log("a: "+a);
for (var i=1 ; i < s ; i++) {
var t=expmod(apowq, 1<<i, n);
if (t===n-1 || t===1) {
return true;
}
}
return false;
}
for (var q=n-1, s=0 ; !isOdd(q) ; q/=2, s++);
for (var i=0, t=true ; i<20 && t ; i++)
t=t && test(q, s);
return t;
}
function streams(n) {
function p(n) {
return {
v: n,
n: function() {
for (n+=2 ; !isPrime(n) ; n+=2);
return p(n);
}
}
}
var pr=p(3);
do {
if (pr.v * pr.v > n) {
return true;
}
if (n%pr.v===0) {
return false;
}
}
while (pr=pr.n());
}
var isPrime=memoize(function(n) {
n=Math.abs(n);
if (n===2) {
return true;
}
if (n < 2 || n%2 === 0) {
return false;
}
if (n < 5000 || n > Math.exp(2, 26)) {
return streams(n);
}
return millerRabin(n);
});
function memoize(f) {
var cache=[];
return function(arg) {
return (arg in cache) ? cache[arg] : cache[arg]=f(arg);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment