Question

I need an answer in C++, please

TITLE

PRIME FACTORIZATION USING AN ARRAY-BASED STACK

INTRODUCTION

This project revisits one of the problems in Project 2, and it will re-use a function within the solution developed there.

An integer is prime if it is divisible only by itself and 1. Every integer can be written as a product of prime numbers, unique except for their order, called its prime factorization. For example,

1776 = 37 x 3 x 2 x 2 x 2 x 2.

DESCRIPTION

Design, implement, document, and test an interactive program that reads positive integers from the terminal and writes their prime factorizations to the screen. The program should list the factors of each integer in decreasing order, as in the example above, and should terminate when the user enters 0 or a negative value.

INPUT

The program's input is positive integers, entered from the terminal, terminated by 0 or a negative value.

OUTPUT

The program's output consists of prompts for the input values and the input values' prime factorizations. It writes this output to the terminal.

ERRORS

The program can assume that its input is integers; it need not detect any errors.

EXAMPLE

A session with the program might look like this:

  Enter a positive integer (0 to stop): 1776
    Prime factors: 1776 = 37 x 3 x 2 x 2 x 2 x 2

  Enter a positive integer (0 to stop): 6463
    Prime factors: 6463 = 281 x 23

  Enter a positive integer (0 to stop): 349856
    Prime factors: 349856 = 29 x 29 x 13 x 2 x 2 x 2 x 2 x 2

  Enter a positive integer (0 to stop): 36423479
    Prime factors: 36423479 = 36423479

  Enter a positive integer (0 to stop): 1
    Prime factors: 1 = 1

  Enter a positive integer (0 to stop): 0
    

OTHER REQUIREMENTS

Implement a stack abstract data type in a class in which a typedef statement specifies the type of the stack's items. Use a sequential (array-based) stack implementation. As the program identifies prime factors, it should save them by pushing them onto a stack of integers provided by this class.

If d >= 2 is the smallest integer that divides an integer n, then d is prime. Therefore the program can identify prime factors (in ascending order) by repeatedly identifying the smallest factor of the target value and then dividing the target value by the factor. The program need not test that these smallest factors are prime or attempt to list only prime values; this will happen automatically.

Thus, to identify the prime factors of n, first find the smallest factor that divides n, push it onto the stack, and divide n by the factor. Then find the smallest factor of the new value of n; handle it the same way. Continue in this way until n = 1. Then pop and print the values until the stack is empty.

This scheme identifies prime factors in order of increasing magnitude; saving the values on the stack and then popping and printing them displays them in decreasing order, as specified.

HINT

Recall that you wrote a function that returns the smallest factor of its positive integer argument back in Project 2. You can re-use that function in this project.

HAND IN

See About Programming Assignments for a description of what to hand in: design document, user document, code, tests, and summary.

Question: If we wanted to report each integer's prime factors in increasing order, would the stack be necessary or helpful? Explain.

Project 2:

PRIME FACTORIZATION

The smallest nontrivial factor of a positive integer is necessarily prime. (Can you prove this?) Write a program that takes advantage of this fact in a recursive function that writes the prime factors of an integer to the terminal in ascending order.

A run of the program that exercises this function might look like this:

          Enter a positive integer: 5432
          The prime factors of 5432 are 2 2 2 7 97
    

Hint: Begin by writing a function that returns the smallest factor (greater than 1) of its positive integer argument. The recursive function will call this one.

QUESTION: How would you modify the function to print the prime factors in descending order?

Answer 1

Program to print the prime factors for a given number.

Explaination)

The program takes an integer n as input from the user and print the prime factors for that number.

A stack vector is implemented to store the numbers so that we can sort the number accordingly.

The program terminates when someone enters 0 or negative value.

// Program to print all prime factors 
# include <stdio.h> 
# include <math.h> 
# include <iostream>
#include <bits/stdc++.h> 


using namespace std;
// A function to print all prime factors of a given number n 
void primeFactorization(int n) 
{ 
    
    //stack to store data so we can sort the array.
    vector <int> primes; 
    int temp;
    
    if (n != 2 && n > 0 ) {
    // Print the number of 2s that divide n 
    while (n%2 == 0) 
    {   
        primes.push_back(2);
        n = n/2; 
    } 
    
    
    // n must be odd .
    for (int i = 3; i <= sqrt(n); i = i+2) 
    { 
        // While i divides n, print i and divide n 
        while (n%i == 0) 
        {   
            primes.push_back(i);
            n = n/i;
        } 
    } 
  
    if (n > 2) 
            primes.push_back(n);
            
    cout << "numbers in ascending order\n";
    
    //you can use sizeof(primes) instead of 7 in for loop
    
    for (int j=0;j<7;j++) {
        printf("%d\t",primes[j],"\n");
    }
    
    //code to sort array in descending order  
    for(int i=0;i<= sqrt(n);i++)
            {           
                    for(int j=i+1;j<= sqrt(n);j++)
                        {
                                if(primes[i]<primes[j])
                                    {
                                        temp  =primes[i];
                                        primes[i]=primes[j];
                                        primes[j]=temp;
                                    }
                        }
            }

    //you can use sizeof(primes) instead of 7 in for loop
    
    cout << "\nnumbers in descending order\n";
    for (int j=0;j<7;j++) {
        printf("%d\t",primes[j]);
    }
    }
    else {
        printf("program terminated");
    }
} 
  
  
using namespace std;
int main() 
{ 
    int n;
    cout << "Enter the number:";
    cin >> n;
    primeFactorization(n); 
    return 0;
}

Some screeshots for output.