Last active
August 29, 2015 14:17
-
-
Save owenversteeg/09ae1495ab5cf0937278 to your computer and use it in GitHub Desktop.
eulerphi
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; | |
for (var i=Math.floor(n)+1; i<9007199254740992; i++) { | |
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; | |
} | |
function factor_(n) { | |
var s = n.toString().replace(/^\s+|\s+$/g,''); | |
var f=parseFloat(s), len=s.length; | |
if (s=='' ) return 'Empty input' | |
if (isNaN(f) || f%1 || s.match(/\D/)) | |
return 'Invalid input [expected an integer, digits only]' | |
if (s.length>20 ) return 'Invalid input [exceeded the 20 digits maximum]' | |
if (f<9007199254740992) return factor(parseInt(s,10)); | |
var lastDigit = parseInt(s.charAt(len-1),10); | |
if (lastDigit==1 || lastDigit==3 || lastDigit==7 || lastDigit==9) { | |
if (isPrimeMR15(s)) return s; | |
} | |
var minFactor = leastFactor_(s).toString(); | |
if (s==minFactor) return s; | |
var x = str2bigInt(s,10,len); | |
var y = str2bigInt(minFactor,10,len); | |
var q = str2bigInt('1',10,len); | |
var r = str2bigInt('1',10,len); | |
divide_(x,y,q,r); | |
return minFactor+'*'+factor_(bigInt2str(q,10)); | |
} | |
function totient_16digits(n) { | |
var n = parseInt(n,10); | |
var res, factors, f0=1, f1=1, phi=n; | |
if (n<1) return 0; | |
if (n<3) return 1; | |
res = factor_(n); | |
if (res.indexOf('*')==-1) return n-1; | |
factors = res.split('*').sort(numericSortOrder); | |
for (var i=0; i<factors.length; i++) { | |
f0 = f1; | |
f1 = parseInt(factors[i],10); | |
if (f1!=f0) phi = (phi/f1)*(f1-1); | |
} | |
return Math.round(phi); | |
} | |
function numericSortOrder(x,y) {return x-y;} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment