Thread: 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

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

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;  
}

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

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