Integer Factorization

This is a discussion on Integer Factorization within the C++ Programming forums, part of the General Programming Boards category; Hi everybody, I need a little help and advice with this code snippet. I want the function to take an ...

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    8

    Integer Factorization

    Hi everybody, I need a little help and advice with this code snippet.

    I want the function to take an integer, return a pointer to an array of ints on the heap. This array will contain all of the factors.
    Please point out where I could optimize or beautify my code.

    Anyway, here it is:

    Code:
    const int MaxFactors = 30;
    
    int* Factorize(int Number)
    {
      int* Factors = new int[MaxFactors];
      int* pFactor;
      int possibleFactor = 3;
    
      int counter = 0;
      int startNumber = Number;
    
      if(Number == 1)
        {
          pFactor = new int(1);
          Factors[counter] = *pFactor;
          delete pFactor;
          pFactor = 0;
    
          counter++;
        }
      for(counter; counter < MaxFactors; )
        {
          if(Number % 2 == 0)
    	{
    	  pFactor = new int(2);
    	  Factors[counter] = *pFactor;
    	  delete pFactor;
    	  pFactor = 0;
    	  Number /= 2;
    
    	  counter++;
    	}
          else
    	break;
        }
    
      for(counter; counter < MaxFactors && possibleFactor <= Number; )
        {
          if(Number % possibleFactor == 0)
    	{
    	  while(Number % possibleFactor == 0)
    	    {
    	      pFactor = new int(possibleFactor);
    	      Factors[counter] = *pFactor;
    	      delete pFactor;
    	      pFactor = 0;
    	      
    	      Number /= possibleFactor;
    	      counter++;
    	    }
    	}
          else
    	possibleFactor += 2;
        }
      if(Factors[0] == startNumber)
        {
          // Primenumber, no factors
          if(Factors[0] == 2)
    	{
    	  pFactor = new int(2);
    	  Factors[0] = *pFactor;
    	  delete pFactor;
    	  pFactor = 0;
    	}
          else if(Factors[0] == 1)
    	{
    	  pFactor = new int(1);
    	  Factors[0] = *pFactor;
    	  delete pFactor;
    	  pFactor = 0;
    	}
          else
                 return Factors;
        } // end if(Factors[0] == startNumber)
    
      return Factors;
    } // end Factorize(int Number)
    -- Placid

  2. #2
    Registered User
    Join Date
    Jul 2003
    Posts
    8
    Thanks a lot!

    I sorta typed that almost out of the book I'm studying, and I should've checked it more thorough I guess...

    But besides that, is there anything that could be better with the algorithm? Could the ugly MaxFactors constant be avoided via a linked list? If so, would you have done it?

    -- Placid

  3. #3
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    A const isn't ugly. A #define is ugly. A global variable is (usally) ugly. The const is fine, and no, it couldn't have been avoided with a linked list, although a linked list could have a place in an application like this if you needed the factors for something other than printing to the screen.
    Away.

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    The ugly MaxFactors constant, along with the problem of there being such a thing as a maximum number of factors, and the problem of telling the calling program how many factors you actually found along with , and this is a big one, the requirement of callers to clean up the memory allocated by factors can be solved with vectors.

    The other trick to note, is that if n has no factors < sqrt(n) then ether sqrt(n) is a factor (n is the square of a prime), or n is a prime. sqrt is mildly expensive so I jumped through some hoops to minimse the number of times it's called.
    Code:
    #include <iostream>
    #include <stdlib.h>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    
    typedef std::vector<unsigned> factors_t;
    
    factors_t factors(unsigned n) {
        if(n < 2) return factors_t(1,n); 
        factors_t v; 
        while(n % 2 == 0) { v.push_back(2); n/=2; }
    
        unsigned max = static_cast<unsigned>(ceil(sqrt(n)));
        for(unsigned fact = 3; fact <= max; fact += 2) {
            if(n % fact == 0) {
               do { 
                   v.push_back(fact); 
                   n/=fact; 
               } while(n % fact == 0);
               max = static_cast<int>(ceil(sqrt(n)));
            }   
        }
        if(n > 1) v.push_back(n);    
        return v;
    }
    
    
    int main(int argc, char *argv[]) {
      unsigned n = (argc>1)?atoi(argv[1]):2*2*3*5*7*13*17;
      factors_t v = factors(n);
      std::cout << n << " has " << v.size() << " factors" << std::endl;
      std::copy(v.begin(),v.end()-1,std::ostream_iterator<unsigned>(std::cout,"*"));
      std::cout << v.back() << std::endl;
      return 0;  
    }

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    8
    Thanks for the input!

    Well I'm actually using this piece of code for something else: I'm reducing a rational number with the use of this function. In the Rational class the memory is released via the deconstructor, so that's not the biggest problem IMHO.
    I agree though that the function that allocates should be the one which frees memory, but sometimes that's impossible. (Perhaps a sign of bad design? I hope not...)

    Vectors seems to have a multitude of uses; I'll probably look into them in the near future . Thanks for the pointer grib.

    --Placid

  6. #6
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    Then the first thing I would look at is the binary euclid's algorithm. You don't need any aditional storage for this, just your two ints. Boost has an interesting rational class, for the simple case of a pair of ints. You will almost certainly feel the pull of arbitrary precision calling you eventually, might be good to get to know the fast. portable, yet GPL only gmp

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 10:42 AM
  4. No Match For Operator+ ???????
    By Paul22000 in forum C++ Programming
    Replies: 24
    Last Post: 05-14-2008, 11:53 AM
  5. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 10:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21