Calculating Factors

[evilguru]

Hi, I need a way of working out what two numbers can be multiplied together to create another number, e.g.
If my number was 18
I could do:
1*9
2*9
3*6
Does anyone know of a Javascript function which is able to work this out given a number?

[Philip M]

http://javascript.internet.com/calculators/factors.html

[evilguru]

Thanks for the link, however it does not seem to work fully, if I type in 100 and ask it to give me the factors it gives:

Number: 100 is Even

Factors Are:

(50,2)(25,4)(20,5)

But, last time I checked 10 x 10 would go into 100.

[kansel]

Easy enough to fix. Make the changes in red to that script mentioned above.

function calc() {
var dnum = ((eval(document.res.inpa.value)) / 2);
var i;
var pol;
var inum = (Math.round(dnum));
if (inum == dnum) {
document.res.rses.value="Number: " + (eval(document.res.inpa.value)) + " is Even\n\n";
}
else {
document.res.rses.value="Number: " + (eval(document.res.inpa.value)) + " is Odd\n\n";
}
document.res.rses.value += "Factors Are:\n\n";
var num = Math.round(eval(document.res.inpa.value));
for (i = 1; i < (num / 2); i++) {
var chkd = Math.round(num / i);
var inn = Math.round(num / i);
var outt = (num / i);
if (inn == outt && chkd >= i) {
document.res.rses.value = document.res.rses.value + "(" + (num/i) + "," + i + ")";
      }
   }
}

Starting the loop index at 1 instead of 2 will include 1xN and changing chkd > i to chkd >= i will include squares - try 9 or 25 in the original script for a lark.

I was going to point to a prime factorization script that I wrote for a friend a couple years ago but it doesn't do exactly what you want - it only finds prime factors. 100 => 5, 5, 2, 2. But it does it FAST. It works very well for large numbers.

[ca_redwards]

This function returns the prime factorization of the number passed into it.

function prime(p){
  if(!prime[p]){
    var f=2;
    if(p%2)
      for(f=3;(p%f)&&(f*f<=p);f+=2);
    if(f*f>p){
      prime[p]=p      
    }
    else{
      prime[p]=(prime[f]=f)+'*'+prime(p/f)      
    }
  }
  return prime[p]  
}

[kansel]

ca_redwards:

Your function consistently beats mine by a handful of loop iterations and recursive calls.

I tested with this number: 994070203729722
Yours ran 18875 total loop iterations with 5 recursive calls.
Mine ran 18939 loops with 10 recursive calls.

Both functions found these primes: 2, 3, 3, 7, 11149, 707637103

Mine:

function prime(number){
  var sq = Math.sqrt(number);
  for(var i = 2; i <= sq; i++){
    if(number%i == 0 && number != i){
      return prime(i) + " * " + prime(number/i);
    }
    if(i>2) i++;
  }
  return number;
}

[ca_redwards]

A few notes about these functions...

Originally Posted by kansel

function prime(number){
  var sq = Math.sqrt(number);
  for(var i = 2; i <= sq; i++){
    if(number%i == 0 && number != i){
      return prime(i) + " * " + prime(number/i);
    }
    if(i>2) i++;
  }
  return number;
}

Originally Posted by ca_redwards

function prime(p){
  if(!prime[p]){
    var f=2;
    if(p%2)
      for(f=3;(p%f)&&(f*f<=p);f+=2);
    if(f*f>p){
      prime[p]=p      
    }
    else{
      prime[p]=(prime[f]=f)+'*'+prime(p/f)      
    }
  }
  return prime[p]  
}

Your code invokes the Math.sqrt() function, then repeatedly compares the trial factor against the previously stored result. I expect that Math.sqrt() has some significant overhead in its calculation, so I repeatedly compute the square at each comparison. A modern CPU can evaluate a product of two numbers in a single instruction, but calculating a root may require several instructions. I tried both, and found that avoiding Math.sqrt() cut the runtime in half.

When iterating through all the possible odd factors beyond 2, your code repeatedly compares the trial factor against 2, whereas mine does not.

Your function returns a non-prime as a product of two recursive results, but in the same case, mine employs only the second recursive term. The first term, known to be prime, is stored into an enumerated property of the function itself. And the final result is stored likewise.

Thus, before factoring anything, my function first checks to see if the answer is known. If so, it is summarily returned. My function learns from experience.

There might be an even better solution where possible factors are rejected if they are known to be factorable...

What do you think?

[evilguru]

I have managed to get the code down to:

function calc() {
	var i;
	var num = Math.round(100);
	for (i = 1; i < (num / 2); i++) {
		var inn = Math.round(num / i);
		var outt = (num / i);
		if (inn == outt && inn >= i) {
			document.getElementById('fact').value = document.getElementById('fact').value + "(" + (num/i) + "," + i + ")";
		}
	}
}

However, does anyone know of a solution which does not rely on a fault of the JavaScript language (when rounding a number if it is .5 you should always round towards the even number according to the IEEE specs).

[TNO]

var roundUp = Math.ceil(x); 
var roundDown = Math.floor(x); 
var round = Math.round(x);

[mnkyslut]

I realize that you've already resolved your problem, but perhaps this recursive method will be helpful to you or anyone else that was purusing this thread for such. Also, before anyone points it out, this is Java, not Javascript like the rest of the source provided in this thread.

private int d=2;
public String primeFactorRec(int n) {
        if(n==1) {return "";}
        else if(n%d==0) {n=n/d; return ((String.valueOf(d)+" "+primeFactorRec(n)).trim()).replace(' ','*');}
        else {d++; return primeFactorRec(n);}
}

It starts the first factor at 2, outside of the method, for obvious reasons.