Last active
September 11, 2015 14:48
-
-
Save itsgreggreg/ce33a28e04fdddc11593 to your computer and use it in GitHub Desktop.
JS functional find prime factors
This file contains hidden or 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
// Calling find_prime_factors on numbers that functional languages can easily handle | |
// will cause a stack size exception. JS can't handle functional programming. :) | |
// http://jsbin.com/qakodivepe/edit?js,console | |
// try: | |
// primeFactors(10) | |
// primeFactors(7775460) | |
// primeFactors(7919) | |
// primeFactors(1056884) <- Boom, stack size exception | |
// Entry point | |
function find_prime_factors(num){ facs(num, 2) } | |
// n is current number | |
// f is factor to check | |
function facs(n, f) { | |
// if f is bigger than half n, n is prime... return it | |
if (f > n / 2) return [n]; | |
// if f is a factor of n | |
if (n % f === 0) { | |
// return it and the prime factors of n/f | |
return [f].concat(facs(n / f, 2)); | |
} else { | |
// otherwise try the next factor, skipping all evens except 2 | |
return facs(n, f + (f === 2 ? 1 : 2)); | |
} | |
}; | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment