Flash Website Builder- Trendy Site Builder is a Flash Site Building tool that helps users build stunning websites. Check Out Custom Custom Logo Design by LogoBee. Website Design and Free Logo Templates available.
 CodingForums.com Calculating Factors

Before you post, read our: Rules & Posting Guidelines

Enjoy an ad free experience by logging in. Not a member yet? Register.
 09-23-2005, 07:06 PM PM User | #1 evilguru Regular Coder   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?
 09-23-2005, 07:27 PM PM User | #2 Philip M Supreme Master coder!     Join Date: Jun 2002 Location: London, England Posts: 17,473 Thanks: 200 Thanked 2,469 Times in 2,447 Posts
 09-26-2005, 04:43 PM PM User | #3 evilguru Regular Coder   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: Code: ```Number: 100 is Even Factors Are: (50,2)(25,4)(20,5)``` But, last time I checked 10 x 10 would go into 100.
 09-26-2005, 10:52 PM PM User | #4 kansel Regular Coder   Join Date: Jul 2002 Location: Kansas, USA Posts: 465 Thanks: 0 Thanked 45 Times in 44 Posts Easy enough to fix. Make the changes in red to that script mentioned above. 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 + ")"; } } }``` 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.
 09-27-2005, 06:33 PM PM User | #5 ca_redwards Regular Coder   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] }```
 09-27-2005, 09:33 PM PM User | #6 kansel Regular Coder   Join Date: Jul 2002 Location: Kansas, USA Posts: 465 Thanks: 0 Thanked 45 Times in 44 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; }```
09-27-2005, 10:12 PM   PM User | #7
ca_redwards
Regular Coder

Join Date: Dec 2002
Posts: 169
Thanks: 0
Thanked 0 Times in 0 Posts
Prime factorization...

A few notes about these functions...
Quote:
 Originally Posted by kansel 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; }```
Quote:
 Originally Posted by ca_redwards 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] }```
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?

Last edited by ca_redwards; 09-27-2005 at 10:41 PM..

 09-28-2005, 02:46 PM PM User | #8 evilguru Regular Coder   Join Date: Jan 2005 Posts: 113 Thanks: 0 Thanked 0 Times in 0 Posts I have managed to get the code down to: 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 + ")"; } } }``` 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).
 09-28-2005, 03:32 PM PM User | #9 TNO Regular Coder   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);```
 10-19-2005, 09:29 AM PM User | #10 mnkyslut New to the CF scene   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. 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);} }``` It starts the first factor at 2, outside of the method, for obvious reasons.

 Bookmarks

 Thread Tools Rate This Thread Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home :: Client side development     JavaScript programming         DOM and JSON scripting         Ajax and Design         JavaScript frameworks         Post a JavaScript     HTML & CSS     XML     Flash & ActionScript         Adobe Flex     Graphics and Multimedia discussions     General web building         Site reviews         Building for mobile devices :: Server side development     Apache configuration     Perl/ CGI     PHP         Post a PHP snippet     MySQL         Other Databases     Ruby & Ruby On Rails     ASP     ASP.NET     Java and JSP     Other server side languages/ issues         ColdFusion         Python :: Computing & Sciences     Computer Programming     Computer/PC discussions     Geek News and Humour Web Projects and Services Marketplace     Web Projects         Small projects (quick fixes and changes)         Medium projects (new script, new features, etc)         Large Projects (new web application, complex features etc)         Unknown sized projects (request quote)         Vacant job positions         Looking for work/ for hire         Project collaboration/ partnership         Paid work offers and requests (Now CLOSED)     Career, job, and business ideas or advice     Domains, Sites, and Designs for sale         Domains for sale         Websites for sale         Design templates and graphics for sale :: Other forums     Member Offers     Forum feedback and announcements

All times are GMT +1. The time now is 09:00 PM.