C++ factorization

[nparrish15]

I've been working on a program and have hit a roadblock. I know conceptually what to do, but I'm having trouble implimenting it.
Ok, so what it's suppose to do is take them randomly generated numbers that have been put in arrayints and factor them. This right now for an example if the number is 100 it will print out: 2 * 50 4 * 25 5 * 20 10 * 10 1 * 100. What I want it to print out is: 2 * 2 * 5 * 5 (doesn't have to be in that order I guess) but I'm having trouble with this. It's probably something simple that I'm overlooking but if anybody could help with it that would be great. Thanks!
Conceptually, I know I need to take the number I get from the if((arrayints[i] % j) == 0 && arrayints[i] != j) and run it back through here. Ex. 100, you would get factor1 = 2, and factor2 = 50, so I need to somehow run factor2 back through the if statement without incrementing j. (hopefully you understand what I mean lol)

for (int i = 0; i < integerIn; i++)
{
cout << "The factors for " << arrayints[i] << " are: ";
for (int j = 2; j <= floor (sqrt((double)integerIn)); j++)
{
if ((arrayints[i] % j) == 0 && arrayints[i] != j)
{
factor1 = j;
factor2 = arrayints[i]/j;
cout << factor1 << " * " << factor2 << " ";
}
}
factor1 = 1;
factor2 = arrayints[i];
cout << factor1 << " * " << factor2 <<endl;
}

[buffbill]

Simplistically if you use the modulous operator in a for loop stating with 2 and end condition of say <10 you might identify some factors
e.g.

int factor[10]={0};
cout<<"Enter an integer" ;
cin>>n;
for(int i =2;i<10;i++)
{ if(n%i==0) factor [i]=i;                   //i is a factor, store in factor array
 else continue;                                  //next iteration
}
cout<<"The factors of "<<n<<" are: <<endl;
for(int i =2;i<10;i++)
cout<<factor[i]<<" ";  //print out the factor array 

[jRaskell]

A recursive function would be more suitable to what you're trying to do. Something like:

#include <iostream>
#include <vector>
using namespace std;
vector<int> getFactors(int x){
	
	int j = 2;
	vector<int> vFactors;
	do{
		if(x%j == 0){
			vFactors = getFactors(x/j);
			vFactors.insert(vFactors.begin(), j);
			return vFactors;
		}
		j++;
	}while(j<(x/2));
	vFactors.insert(vFactors.begin(), x);
	return vFactors;

}



int _tmain(int argc, _TCHAR* argv[])
{
	int x;
	vector <int> myFactors;
	do{

		cout << "Enter a number: ";
		cin >> x;
		cout << endl << "factors: ";
		myFactors.clear();

		if(x>0){
			myFactors = getFactors(x);
			for(unsigned int i = 0; i < myFactors.size(); i++)
				cout << myFactors[i] << " ";
			cout << endl;
		}

	}while(x!=0);


	return 0;
}

Edit: There is a flaw in my function though when inputting numbers that are a power of 2.

[jsmith]

Recursion is not needed at all, nor even an array.

If you start at 2 and go up, the first two factors you will find are m and n, (m<=n) where m must be prime and n may not be. Then repeat the same algorithm on n. Continue doing so until both numbers are prime.

[jRaskell]

If you start at 2 and go up, the first two factors you will find are m and n, (m<=n) where m must be prime and n may not be. Then repeat the same algorithm on n. Continue doing so until both numbers are prime.

Perform some algorithm on the input, then repeat that algorithm on the output until some condition is met.

That's the very definition of recursion. Is it needed for this rather simple scenario? Of course not. Is it suitable? Absolutely.

[buffbill]

I agree with jsmith recursion is not needed.
the algorithm seems to be:
1. Check that the number generated is or is not prime. If it is, the problem is solved. The number has no factors. e.g. if n=151 n is prime - no factors.
2. Try to divide 2 (the 1st and only even prime) into the number as many times as possible without leaving a remainder any time. Divide n by 2 each time to progressively halve the value of n each time. i.e. (n/=2;) Each time you succeeed, print 2. e.g. if n = 144 you would get 2 2 2 2 . You could use a while(n>1) loop to controll this. If the original n is odd, 2 will not be divided into n in this 1st while loop and n will remain unchanged.
3. Pass on to a similar while loop and progressively divide the next prime number into the reduced n. Divide n by the current array prime (in this case 3) each time there is no remainder (as with 2 above)This could be handled by a for loop iterating through the array of primes.
With n = 144 you would get 3 3. So factors of 144 would be 2 2 2 2 3 3 which when multiplied together would produce 144 as a check.
You need to generate each succeeding prime with a prime function or alternatively load an array with all the prime numbers between your desired bounds and compare n with each prime factor until the two equal
e.g. if the number was 366 the routine would return 2 3 61.
Probably the easiest way to control this would be with a simple for loop.
If the chosen bounds were 0 --> 1000 , since there are 168 primes in this range the fore loop inside the while loop would look like:

 for(i=3;i<168;i++) //to iterate through the array of primes.
  {if (array[i]==n)
  cout<<n<<" ";
  break;} 

e.g. if n was 999 the factors would be 3 3 3 37.
if n was 998 the factors would be 2 499
4. Multiply the factors together to check that their product = n.

[turbozedd]

Having fun fighting about what is and is not recursion?

It is tail recursion...the happy kind that you can do in a loop.

The following is the easiest algorithm. If you have big (really big) primes there are much better algorithms for factoring. An easy improvement of this is having a lookup list of primes instead of dividing by odd numbers.

i=0;
while(!(n%2)) { factors[i]=2; n/=2; i++;}
max=sqrt(n);
for(int j=3; j<max j+=2){
    while(!(n%j)) { factors[i]=j; n/=j; i++;}
}

[jsmith]

Finally someone saw the light.

Tail recursion is the easiest form of recursion to refactor into a simple loop.

int n = 21842431;   // Assume n is the number to factor
int lastFactor = 2;
while( lastFactor < n ) {
    if( n % lastFactor == 0 ) {
         cout << lastFactor << ' ';
         n /= lastFactor;
    } else 
        ++lastFactor;
}

if( n != 1 )
    cout << n;

Or replace the above cout's with vector push_backs if you want to store the factors in a container.

[buffbill]

Brilliant- never having heard of tail recursion, have now started to learn about it. None of my books mention it. As a matter of interest do the last 2 lines take care of the situation where n (however large ) is a prime? (e.g when you mod by 2 only once and the resultant n is prime)
rgds.

[jsmith]

The last two lines output the last factor. Consider n = 21 = 3 * 7.

When last factor becomes 3, n % 3 == 0, so we output 3, then divide
n by 3 (so n == 7 ).

We continue to loop, checking 3, 4, 5, and 6 against 7. None divide 7
evenly. When ++lastFactor makes lastFactor == 7, the while loop
terminates. But we still haven't output 7 (which the the value of n).

[buffbill]

Ok - yes I understand - many thanks;
rgds

[turbozedd]

You can save lots of time by only checking odds, lastfactor+=2, but you have to write 2 as a separate case. This will make a noticeable difference if you have to factor many numbers or very large numbers.

unsigned long long n = -1; // Assume n is the number to factor 
unsigned long long lastFactor = 3; //skip evens

// 2
while (n % 2 == 0) {
    cout << lastFactor << ' ';
    n /= lastFactor;
}

// 3 + 2*n
while (lastFactor < n) {                          //jsmith
    if (n % lastFactor == 0) {                    //jsmith
        cout << lastFactor << ' ';                //jsmith
        n /= lastFactor;                          //jsmith
    } else                                        //jsmith
        lastFactor+=2;    // next odd

}

if (n != 1)                                       //jsmith
    cout << n << "\n";                            //jsmith