Enjoy an ad free experience by logging in. Not a member yet? Register.


Results 1 to 10 of 10
Thread: Calculating Factors

09232005, 06:06 PM #1
 Join Date
 Jan 2005
 Posts
 113
 Thanks
 0
 Thanked 0 Times in 0 Posts
Calculating Factors
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?
09232005, 06:27 PM
#2
09262005, 03:43 PM
#3
 Join Date
 Jan 2005
 Posts
 113
 Thanks
 0
 Thanked 0 Times in 0 Posts
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:
But, last time I checked 10 x 10 would go into 100.Code:Number: 100 is Even Factors Are: (50,2)(25,4)(20,5)
09262005, 09:52 PM
#4
 Join Date
 Jul 2002
 Location
 Kansas, USA
 Posts
 477
 Thanks
 0
 Thanked 51 Times in 50 Posts
Easy enough to fix. Make the changes in red to that script mentioned above.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.Code: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 + ")"; } } }
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.
09272005, 05:33 PM
#5
 Join Date
 Dec 2002
 Posts
 169
 Thanks
 0
 Thanked 0 Times in 0 Posts
Prime factorization...
This function returns the prime factorization of the number passed into it.
Code: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] }
09272005, 08:33 PM
#6
 Join Date
 Jul 2002
 Location
 Kansas, USA
 Posts
 477
 Thanks
 0
 Thanked 51 Times in 50 Posts
O/t
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:Code: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; }
09272005, 09:12 PM
#7
 Join Date
 Dec 2002
 Posts
 169
 Thanks
 0
 Thanked 0 Times in 0 Posts
Prime factorization...
A few notes about these functions...
Originally Posted by kanselYour 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.Originally Posted by ca_redwards
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 nonprime 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?
Last edited by ca_redwards; 09272005 at 09:41 PM.
09282005, 01:46 PM
#8
 Join Date
 Jan 2005
 Posts
 113
 Thanks
 0
 Thanked 0 Times in 0 Posts
I have managed to get the code down to:
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).Code: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 + ")"; } } }
09282005, 02:32 PM
#9
 Join Date
 Apr 2005
 Posts
 213
 Thanks
 2
 Thanked 1 Time in 1 Post
Code:var roundUp = Math.ceil(x); var roundDown = Math.floor(x); var round = Math.round(x);
10192005, 08:29 AM
#10
 Join Date
 Oct 2005
 Location
 Brockport, NY
 Posts
 2
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.
It starts the first factor at 2, outside of the method, for obvious reasons.Code: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);} }