Simple Prime Factorization

[Kaon Flux]

Dear all,

I am working through the C++ without Fear for beginners book and become stuck.

I am up to recursive functions and prime factorization. Now i understand how prime factorisations are worked out and i understand how to workout the factorisation with recursion but there is an excercise that asks of this...

Modify Example 4.3 so that it uses a nonrecursive solution. You will end up having to write more code. (Hint: To make the job easier, write two func- tions: get_all_divisors and get_lowest_divisor. The main function should call get_all_divisors, which in turn has a loop: get_all_divisors calls get_lowest_divisor repeatedly, each time replacing n with n/i, where i is the divisor that was found. If n itself is returned, then the number is prime, and the loop should stop.

now this is where i get really confused...

2 functions? a loop where on calls the other until the number is prime?? bloody hell....

here is what I have written so far for main().... btw i am on a mac thats why i use system clear....

#include <iostream>
#include <cmath>
using namespace std;

void getAllDivisors(int n);
void getLowestDivisors(int x);


int main()

{

	int n = 0;
	
	system("clear");
	
	while (true) {
		cout << "Enter a number (0 = exit) and press ENTER: ";
		cin >> n;
		if (n == 0)
			break;
		getAllDivisors(n);
		cout << "\n\n";
		}
	cout << endl;
	return 0;

}

ok so now the funcitons

i have tried this.

void getAllDivisors (int n)

{
	double sqrtOfN = sqrt(n);
		
	for (int i = 2; i <= sqrtOfN; i++) {
			
		if (n % i == 0) {
			cout << i << ", ";
			getLowestDivisors(n/i);
			}
		cout << n;
		return;
		
	}
}
				
	
int getLowestDivisors (int x)
	{
		
	double sqrtOfX = sqrt(x);
	
	for (int i = 2; i <= sqrtOfX; i++) {
		if (x % i == 0) {
			cout << i << ", ";
			}
		return x;		
		}
	}

i keep amending the functions over and over now i have been trying this for 2 days and keep getting different results but not what i could get if i used recursive function.

I am not asking people to solve this for me and write it but some guidance would be appreciated.

[D80DSL3A]

Note that both of your functions return on the 1st iteration of their for loops since the return statement is in there.

The idea is to have getLowestDivisor() return the lowest divisor (i) not the value passed in (x).
You want getAllDivisors() to go until getLowestDivisor() returns n. Replace n with n/i if getLowestDivisor() didn't return n.

Too hard to explain all the details, so please just examine this working solution:

int getLowestDivisor(int n)
{
    int i = 2;// value of lowest divisor

    for(i=2; i<=n; ++i)// go all the way to n. We want to find if n itself is the lowest divisor of n
        if( n%i == 0 ) break;// lowest divisor found

    return i;// return the lowest divisor of n found. It may be n itself.
}

void getAllDivisors(int n)
{
    cout << "The divisors of " << n << " are: ";

    while(true)
    {
        int i = getLowestDivisor(n);
        cout << i << ", ";
        if( i == n ) break;// done! n has been factored until it is prime
        n /= i;// replace n with n/i and go again.
    }
    return;
}

P.S. Thanks for the quick exercise.

[Kaon Flux]

I could not get fun2code's explanation to run so I have been racking my brains over the past week and come up with this...

#include <iostream>
#include <cmath>
using namespace std;

void getAllDivisors(int n); // this function calls getLowestDivisor and then divides n by returned value
int getLowestDivisor (int x); // this function checks for divisibilty then returns lowest divisor or 0

int main()

{
	int n;
	system("clear");	// clears console on mac os x terminal
	
	while (true) {
		cout << "Enter a number (0 = exit) and press ENTER: ";
		cin >> n;
		if (n == 0)  // if number entered is n then break while loop and return 0 to end program
			break;
		getAllDivisors(n); // calls getALLDivisors function
		cout << "\n\n";
		}
	cout << endl;
	return 0;  // return 0 and end program
}

void getAllDivisors (int n)  // this function calls getLowestDivisor and then divides n by returned value

{
	while (true) {  // start infinite loop
		
		if (getLowestDivisor(n) == 0) {  // if getLowestDivisor returns 0 then
			cout << n;					// print n
			return;						// end loop and return to main()
		}
		cout << getLowestDivisor(n) << ", ";	// print lowest divisor found in getLowestDivisor function
		n = n / getLowestDivisor(n);
	}
}

int getLowestDivisor (int x)  // this function checks for divisibilty then returns lowest divisor or 0

{
	int sqRootOfX = sqrt(x); // variable is square root of x
	
	for (int i = 2; i <= sqRootOfX; i++)		// for loop 2 to sqroot of x
		{
			if (x % i == 0)			// if i divides equal then return i
				return i;
		}
		return 0;				// else return 0
}