Detect prime numbers (v7)

Revision 7 of this benchmark created by Maxim Zorin on June 25, 2012

Description

Preparation HTML

<script>
//  var arr = [999999000001, 87178291199, 63018038201, 2147483647, 1073676287, 27644437, 1028201, 1011001, 514229, 98689, 1559, 563];
  
  var arr = [27644437, 1028201, 1011001, 514229, 98689, 1559, 563];

  // Code taken from http://ejohn.org/apps/learn/ by John Resig
  
  function isPrime(num) {
   var prime = num != 1; // Everything but 1 can be prime
   for (var i = 2; i < num; i++) {
    if (num % i == 0) {
     prime = false;
     break;
    };
   };
   return prime;
  };
  
  function isPrimeCached(num) {
   if (isPrimeCached.cache[num] !== null) {
    return isPrimeCached.cache[num];
   };
   var prime = num != 1; // Everything but 1 can be prime
   for (var i = 2; i < num; i++) {
    if (num % i == 0) {
     prime = false;
     break;
    };
   };
   isPrimeCached.cache[num] = prime;
   return prime;
  };
  isPrimeCached.cache = {};
  
  // By Devon Govett
  
  function isPrimeFaster(num) {
   var prime = num != 1 || num != 2;
   for (var i = 3; i < num; i += 2) { //ignore even numbers > 2
    if (num % i == 0) {
     prime = false;
     break;
    }
   }
   return prime;
  }
  
  function isPrimeFasterCached(num) {
   if (isPrimeFasterCached.cache[num] !== null) {
    return isPrimeFasterCached.cache[num];
   };
  
   var prime = num != 1 || num != 2;
   for (var i = 3; i < num; i += 2) { // ignore even numbers > 2
    if (num % i == 0) {
     prime = false;
     break;
    }
   }
  
   isPrimeFasterCached.cache[num] = prime;
   return prime;
  };
  isPrimeFasterCached.cache = {};
  
  
  // Code by Devon Govett — http://twitter.com/devongovett/status/20019256843, inspired by http://mths.be/ahf
  
  function isPrimeRegex(n) {
   return Array(n + 1).join('1').search(/^1?$|^(11+?)\1+$/) === -1;
  };
  
  function fermat(p) {
   return (Math.pow(4, p) % p) === (4 % p);
  }
  
  function fermat_simplified(p) {
   return (Math.pow(4, p - 1) % p) === 1;
  }


function isPrime_TrialDivision(n) {
        var primes = arguments.callee.primes || (arguments.callee.primes = [2, 3]);
        if (n <= 1) return false;
        
        var i, p, m, mIsPrime;
        for (i = 0, p; (p = primes[i]) && (p*p <= n); i++)
                if (n % p === 0) return false;
        if (!p)
                for (m = primes[primes.length-1] + 2; m*m <= n; m += 2) {
                        mIsPrime = true;
                        for (i = 0, p; (p = primes[i]) && (p*p <= m); i++)
                                if (m % p === 0) { mIsPrime = false; break; }
                        if (mIsPrime) {
                                primes[primes.length] = m;
                                if (n % m === 0) return false;
                        }
                }
        return true;
}
</script>

Test runner

var i = arr.length;
while (i--) {
 isPrime(arr[i]);
};

var i = arr.length;
while (i--) {
 isPrimeCached(arr[i]);
};

var i = arr.length;
while (i--) {
 // only for small numbers
 if (arr[i] < 1000)
   isPrimeRegex(arr[i]);
};

var i = arr.length;
while (i--) {
 isPrimeFaster(arr[i]);
};

var i = arr.length;
while (i--) {
 isPrimeFasterCached(arr[i]);
};

// a^(p) mod p = a mod p
var i = arr.length;
while (i--) {
 fermat(arr[i]);
};

// a^(p-1) mod p = 1
var i = arr.length;
while (i--) {
 fermat_simplified(arr[i]);
};

var i = arr.length;
while (i--) {
 isPrime_TrialDivision(arr[i]);
};

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Devon Govett on August 1, 2010
• Revision 2: published by Devon Govett on August 1, 2010
• Revision 4: published by Felix Böhm on August 3, 2010
• Revision 7: published by Maxim Zorin on June 25, 2012
• Revision 10: published on October 10, 2014
• Revision 11: published by Sanel Deljkic on February 12, 2015