Skip to content

Instantly share code, notes, and snippets.

@itsgreggreg
Last active September 11, 2015 14:48
Show Gist options
  • Save itsgreggreg/ce33a28e04fdddc11593 to your computer and use it in GitHub Desktop.
Save itsgreggreg/ce33a28e04fdddc11593 to your computer and use it in GitHub Desktop.
JS functional find prime factors
// 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