Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 10 of 10
  1. #1
    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?

  • #2
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    17,918
    Thanks
    203
    Thanked 2,531 Times in 2,509 Posts

  • #3
    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.

  • #4
    Regular Coder
    Join Date
    Jul 2002
    Location
    Kansas, USA
    Posts
    487
    Thanks
    0
    Thanked 54 Times in 53 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.

  • #5
    Regular Coder
    Join Date
    Dec 2002
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Thumbs up 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]  
    }

  • #6
    Regular Coder
    Join Date
    Jul 2002
    Location
    Kansas, USA
    Posts
    487
    Thanks
    0
    Thanked 54 Times in 53 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;
    }

  • #7
    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 09:41 PM.

  • #8
    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).

  • #9
    TNO
    TNO is offline
    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
    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.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •