For a given integer n>1, the smallest integer d>1 that divides n is a prime fact

Question

For a given integer n>1, the smallest integer d>1 that divides n is a prime factor. We can find the prime factorization of n if we find d and then replace n by the quotient of n divided by d, repeathing this until n becomes 1. Write a program that queries the user for a value for n, determines the prime factorization of n in this manner, but displays the prime factors in descending oder. For example for n = 3960 your program should produce:

11 * 5 * 3 * 3 * 2 * 2 * 2

You must use Nyhoff's Stack class (attached); you can not use the STL stack class.

This is what I have so far;

Explanation / Answer

// A function to print all prime factors of a given number n

void primeFactors(int n)

{

Stack s;

    // Print the number of 2s that divide n

    while (n%2 == 0)

    {

s.push(2);

        n = n/2;

    }

    // n must be odd at this point. So we can skip

    // one element (Note i = i +2)

    for (int i = 3; i <= sqrt(n); i = i+2)

    {

        // While i divides n, print i and divide n

        while (n%i == 0)

        {

s.push( i);

            n = n/i;

        }

    }

    // This condition is to handle the case when n

    // is a prime number greater than 2

    if (n > 2)

s.push( n);

cout << s.top();

s.pop();

while(!s.empty())

{

cout << "*" << s.top();

s.pop();

}

cout << endl;

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.