Question

in C++ Description: 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, repeating this until n becomes 1.

            Write a program that determines the prime factorization of n in this manner, but that displays the prime factors in descending order. (When you find a prime factor, push it on a stack)

            For example, if n is 3960 the prime factorization is

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

            You may use the code for implementing a stack that we used in class, found in the chapter 7 folder

Answer 1

void leastPrimeFactor(int n)

{

    // Create a vector to store least primes.

    // Initialize all entries as 0.

    vector<int> least_prime(n+1, 0);

  

    // We need to print 1 for 1.

    least_prime[1] = 1;

  

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

    {

        // least_prime[i] == 0

        // means it i is prime

        if (least_prime[i] == 0)

        {

            // marking the prime number

            // as its own lpf

            least_prime[i] = i;

  

            // mark it as a divisor for all its

            // multiples if not already marked

            for (int j = 2*i; j <= n; j += i)

                if (least_prime[j] == 0)

                   least_prime[j] = i;

        }

    }

  

    // print least prime factor of

    // of numbers till n

    for (int i = 1; i <= n; i++)

        cout << "Least Prime factor of "

             << i << ": " << least_prime[i] << "\n";

}

  

// Driver program to test above function

int main()

{

    int n = 10;

    leastPrimeFactor(n);

    return 0;

}