Code Renaissance is about building great teams and great software. By exploring best practices, team interactions, design, testing and related skills Code Renaissance strives to help you create the team and codebase that you've always wanted.

Finding Prime Factors in Javascript

As a coding exercise I decided to write a recursive algorithm to find prime factors of numbers. Why? For fun, learning, discovery, mental exercise... take your pick.

Among other things prime factors have cryptographic applications. Also it's a great way to increase your knowledge of a language... among other things I discovered that javascript floating point handles these calculations just fine but after 15 places some numbers have the last digit(s) become 0 e.g. parseInt("10000000000000000",10)+1 == 10000000000000000... it's the only floating point problem I found with this exercise. Other than that the code works well and the app below will factor numbers in real time as you type (and check the results to make they're valid).

Give it at try:
Enter a number to get it's prime factors:


As you can see it's pretty darn fast... results may vary but if you have a recent computer then there shouldn't be a noticeable lag on numbers up to 15 digit primes. Primes take the most calculations; they are verified by attempting division by 2 and then every odd number from 3 to the square root of the number being factored.

Using this method determining that 1243245576856897 is prime only needs 17629844 iterations which takes ~2 seconds on my laptop. 5467154436746477 only takes 5 seconds. If you did every calculation up to half of 5467154436746477, which is what I did at first, it would take a year to verify it was prime (assuming you could keep the javascript running that long).

The amazing thing is that the code that does this is small... This little recursive function does all the calculations:
function primeFactorization(num){
  var root = Math.sqrt(num),  
  result = arguments[1] || [],  //get unnamed paremeter from recursive calls
  x = 2; 
  
  if(num % x){//if not divisible by 2 
   x = 3;//assign first odd
   while((num % x) && ((x = x + 2) < root)){}//iterate odds
  }
  //if no factor found then num is prime
  x = (x <= root) ? x : num;
  result.push(x);//push latest prime factor

  //if num isn't prime factor make recursive call
  return (x === num) ? result : primeFactorization(num/x, result) ;
}

3 - What do you think?:

Larry said...

Great code.
Here's an optimized version of it here.
http://bateru.com/news/2012/05/code-of-the-day-javascript-prime-factors-of-a-number/

Anonymous said...

Please can u explain the function

DH said...

Recursive algorithms call themselves until processing is complete. This function first checks to see if the number is divisible by 2. If not it searches for an odd number that its divisible by. When it finds a number that it's divisible by then it adds that number to the results, divides by that number, and calls itself again passing in the result of the division. "num % x" gets the remainder of num divided by x. The way the algorithm is constructed if "num % x" equals 0 then x is prime. Probably the easiest way to understand the code is to step through the code in a debugger. Hope this helps.

Here's a link to a jsfiddle with the (slightly improved) code:

http://jsfiddle.net/CodeRenaissance/9LD2u/

But you can probably debug it easier here:

http://fiddle.jshell.net/CodeRenaissance/9LD2u/show/