Created
May 19, 2015 11:42
-
-
Save volkanozcan/8ee6994224749e2aa280 to your computer and use it in GitHub Desktop.
javascript:isPrime
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Copyright (c) 2011 Alexei Kourbatov, www.JavaScripter.net | |
// function leastFactor(n) returns: | |
// * the smallest prime that divides n | |
// * NaN if n is NaN or Infinity | |
// * 0 if n is 0 | |
// * 1 if n=1, n=-1, or n is not an integer | |
leastFactor = function(n) { | |
if (isNaN(n) || !isFinite(n)) return NaN; | |
if (n==0) return 0; | |
if (n%1 || n*n<2) return 1; | |
if (n%2==0) return 2; | |
if (n%3==0) return 3; | |
if (n%5==0) return 5; | |
var m = Math.sqrt(n); | |
for (var i=7;i<=m;i+=30) { | |
if (n%i==0) return i; | |
if (n%(i+4)==0) return i+4; | |
if (n%(i+6)==0) return i+6; | |
if (n%(i+10)==0) return i+10; | |
if (n%(i+12)==0) return i+12; | |
if (n%(i+16)==0) return i+16; | |
if (n%(i+22)==0) return i+22; | |
if (n%(i+24)==0) return i+24; | |
} | |
return n; | |
} | |
// Optimized version of leastFactor for Opera, Chrome, Firefox. | |
// In these browsers, "i divides n" is much faster as | |
// (q=n/i)==Math.floor(q) than n%i==0 | |
if ( | |
navigator.userAgent.indexOf('Opera') !=-1 | |
|| navigator.userAgent.indexOf('Chrome') !=-1 | |
|| navigator.userAgent.indexOf('Firefox')!=-1 ) | |
{ | |
leastFactor = function(n) { | |
if (isNaN(n) || !isFinite(n)) return NaN; | |
if (n==0) return 0; | |
if (n%1 || n*n<2) return 1; | |
if (n%2==0) return 2; | |
if (n%3==0) return 3; | |
if (n%5==0) return 5; | |
var q, m = Math.sqrt(n); | |
for (var i=7;i<=m;i+=30) { | |
if ((q=n/i)==Math.floor(q)) return i; | |
if ((q=n/(i+4))==Math.floor(q)) return i+4; | |
if ((q=n/(i+6))==Math.floor(q)) return i+6; | |
if ((q=n/(i+10))==Math.floor(q)) return i+10; | |
if ((q=n/(i+12))==Math.floor(q)) return i+12; | |
if ((q=n/(i+16))==Math.floor(q)) return i+16; | |
if ((q=n/(i+22))==Math.floor(q)) return i+22; | |
if ((q=n/(i+24))==Math.floor(q)) return i+24; | |
} | |
return n; | |
} | |
} | |
// Optimized version for Internet Explorer avoids IE's | |
// "slow script" warning at 5000000 script statements | |
// by grouping 48 divisibility checks into a single statement | |
if (navigator.userAgent.indexOf('MSIE')!=-1) | |
{ | |
leastFactor = function(n){ | |
if (isNaN(n)) return NaN; | |
if (n==0) return 0; | |
if (!isFinite(n) || n%1 || n*n<2) return 1; | |
if (n%2==0) return 2; | |
if (n%3==0) return 3; | |
if (n%5==0) return 5; | |
if (n%7==0) return 7; | |
var m = Math.sqrt(n); | |
for (var i=11;i<=m;i+=210) { | |
if (n%i && n%(i+2) && n%(i+6) && n%(i+8)&& n%(i+12)&& n%(i+18)&& n%(i+20)&& n%(i+26) | |
&& n%(i+30) && n%(i+32) && n%(i+36) && n%(i+42) && n%(i+48) && n%(i+50) && n%(i+56) | |
&& n%(i+60) && n%(i+62) && n%(i+68) && n%(i+72) && n%(i+78) && n%(i+86) | |
&& n%(i+90) && n%(i+92) && n%(i+96) && n%(i+98) && n%(i+102)&& n%(i+110)&& n%(i+116) | |
&& n%(i+120)&& n%(i+126)&& n%(i+128)&& n%(i+132)&& n%(i+138)&& n%(i+140)&& n%(i+146) | |
&& n%(i+152)&& n%(i+156)&& n%(i+158)&& n%(i+162)&& n%(i+168)&& n%(i+170)&& n%(i+176) | |
&& n%(i+180)&& n%(i+182)&& n%(i+186)&& n%(i+188)&& n%(i+198)&& n%(i+200) | |
) continue; | |
for (var j=0;j<210;j+=2) {if (n%(i+j)==0) return i+j; } | |
} | |
return n; | |
} | |
} | |
// function isPrime(n) returns: | |
// - false if n is NaN or not a finite integer | |
// - true if n is prime | |
// - false otherwise | |
isPrime = function(n) { | |
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; | |
if (n==leastFactor(n)) return true; | |
return false; | |
} | |
// function factor(n) returns: | |
// * a string containing the prime factorization of n | |
// * n.toString() if the factrization cannot be found | |
function factor(n){ | |
if (isNaN(n) || !isFinite(n) || n%1 || n==0) return n.toString(); | |
if (n<0) return '-'+factor(-n); | |
var minFactor = leastFactor(n); | |
if (n==minFactor) return n.toString(); | |
return minFactor+'*'+factor(n/minFactor); | |
} | |
// function nextPrime(n) returns: | |
// * the smallest prime greater than n | |
// * NaN if this prime is not a representable integer | |
function nextPrime(n){ | |
if (isNaN(n) || !isFinite(n)) return NaN; | |
if (n<2) return 2; | |
n = Math.floor(n); | |
for (var i=n+n%2+1; i<9007199254740992; i+=2) { | |
if (isPrime(i)) return i; | |
} | |
return NaN; | |
} | |
// function nextPrimeTwin(n) returns: | |
// * 2 if n<2 or | |
// * 3 if n<3 or | |
// * 5 if n<5 or | |
// * the smallest twin prime 6i-1 greater than n, for an integer i | |
// * NaN if such a prime is not a representable integer | |
function nextPrimeTwin(n) { | |
if (isNaN(n) || !isFinite(n)) return NaN; | |
if (n<2) return 2; | |
if (n<3) return 3; | |
if (n<5) return 5; | |
for (var i=6*Math.ceil(Math.floor(n+2)/6); i<9007199254740880; i+=6) { | |
if (pscreen(i-1) && pscreen(i+1) && isPrime(i-1) && isPrime(i+1)) | |
return i-1; | |
} | |
return NaN; | |
} | |
// function nextPrimeQuad(n) returns: | |
// * the smallest prime in the next prime quadruplet greater than n | |
// * NaN if such a prime is not a representable integer | |
function nextPrimeQuad(n) { | |
if (isNaN(n) || !isFinite(n)) return NaN; | |
if (n<11) return 11; | |
for (var i=30*Math.ceil(Math.floor(n-10)/30); i<9007199254740880; i+=30) { | |
if (pscreen(i+11) && pscreen(i+13) && pscreen(i+17) && pscreen(i+19) | |
&& isPrime(i+11) && isPrime(i+13) && isPrime(i+17) && isPrime(i+19)) | |
return i+11; | |
} | |
return NaN; | |
} | |
function pscreen(n) { | |
if (n<=19 || n%3 && n%5 && n%7 && n%11 && n%13 && n%17 && n%19) return true; | |
return false; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment