Question

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.

Answer 1

In this question, we need to input a number from user and output its prime factors. But the factors has to outputted in descending order, ie, greatest to smallest. This can be done by using a stack, by pushing each factor into it, and at the end, popping all the factors and printing them. The complete working code for this question is:

This is the class test with some methods to calculate the prime factors:

In this picture, you can see the main/driver code and the output: