Description: For a given integer n > 1, the smallest integer d > 1 that divides
ID: 3811529 • Letter: D
Question
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
driver.cpp
#include <iostream>
using namespace std;
#include "LStack.h"
void print(Stack st)
{ st.display(cout); }
int main()
{
Stack s;
cout << "Stack created. Empty? " << boolalpha << s.empty() << endl;
cout << "How many elements to add to the stack? ";
int numItems;
cin >> numItems;
for (int i = 1; i <= numItems; i++)
s.push(100*i);
cout << "Stack empty? " << s.empty()<< endl;
cout << "Contents of stack s (via print): ";
print(s); cout << endl;
cout << "Check that the stack wasn't modified by print: ";
s.display(cout); cout << endl;
Stack t, u;
t = u = s;
cout << "Contents of stacks t and u after t = u = s (via print): ";
cout << "u: "; print(u); cout << endl;
cout << "t: "; print(t); cout << endl;
cout << "Top value in t: " << t.top()<< endl;
while (!t.empty())
{
cout << "Popping t: " << t.top() << endl;
t.pop();
}
cout << "Stack t empty? " << t.empty()<< endl;
cout << "Top value in t: " << t.top()<< endl;
cout << "Trying to pop t: " << endl;
t.pop();
}
LStack.cpp
#include <new>
using namespace std;
#include "LStack.h"
//--- Definition of Stack constructor
Stack::Stack()
: myTop(0)
{}
//--- Definition of Stack copy constructor
Stack::Stack(const Stack & original)
{
myTop = 0;
if (!original.empty())
{
// Copy first node
myTop = new Stack::Node(original.top());
// Set pointers to run through the stacksÕ linked lists
Stack::NodePointer lastPtr = myTop,
origPtr = original.myTop->next;
while (origPtr != 0)
{
lastPtr->next = new Stack::Node(origPtr->data);
lastPtr = lastPtr->next;
origPtr = origPtr->next;
}
}
}
//--- Definition of Stack destructor
Stack::~Stack()
{
// Set pointers to run through the stack
Stack::NodePointer currPtr = myTop, // node to be deallocated
nextPtr; // its successor
while (currPtr != 0)
{
nextPtr = currPtr->next;
delete currPtr;
currPtr = nextPtr;
}
}
//--- Definition of assignment operator
const Stack & Stack::operator=(const Stack & rightHandSide)
{
if (this !=& rightHandSide) // check that not st = st
{
this->~Stack(); // destroy current linked list
if (rightHandSide.empty()) // empty stack
myTop = 0;
else
{ // copy rightHandSide's list
// Copy first node
myTop = new Stack::Node(rightHandSide.top());
// Set pointers to run through the stacks' linked lists
Stack::NodePointer lastPtr = myTop,
rhsPtr = rightHandSide.myTop->next;
while (rhsPtr != 0)
{
lastPtr->next = new Stack::Node(rhsPtr->data);
lastPtr = lastPtr->next;
rhsPtr = rhsPtr->next;
}
}
}
return *this;
}
//--- Definition of empty()
bool Stack::empty() const
{
return (myTop == 0);
}
//--- Definition of push()
void Stack::push(const StackElement & value)
{
myTop = new Stack::Node(value, myTop);
}
//--- Definition of display()
void Stack::display(ostream & out) const
{
Stack::NodePointer ptr;
for (ptr = myTop; ptr != 0; ptr = ptr->next)
out << ptr->data << endl;
}
//--- Definition of top()
StackElement Stack::top() const
{
if (!empty())
return (myTop->data);
else
{
cerr << "*** Stack is empty "
" -- returning garbage *** ";
StackElement * temp = new(StackElement);
StackElement garbage = *temp; // "Garbage" value
delete temp;
return garbage;
}
}
//--- Definition of pop()
void Stack::pop()
{
if (!empty())
{
Stack::NodePointer ptr = myTop;
myTop = myTop->next;
delete ptr;
}
else
cerr << "*** Stack is empty -- can't remove a value *** ";
}
LStack.h
#include <iostream>
using namespace std;
#ifndef LSTACK
#define LSTACK
typedef int StackElement;
class Stack
{
public:
/***** Function Members *****/
/***** Constructors *****/
Stack();
/*-----------------------------------------------------------------------
Construct a Stack object.
Precondition: None.
Postcondition: An empty Stack object has been constructed
(myTop is initialized to a null pointer).
------------------------------------------------------------------------*/
Stack(const Stack & original);
//-- Same documentation as in Figure 7.8
/***** Destructor *****/
~Stack();
/*------------------------------------------------------------------------
Class destructor
Precondition: None
Postcondition: The linked list in the stack has been deallocated.
------------------------------------------------------------------------*/
/***** Assignment *****/
const Stack & operator= (const Stack & rightHandSide);
/*------------------------------------------------------------------------
Assignment Operator
Precondition: rightHandSide is the stack to be assigned and is
received as a const reference parameter.
Postcondition: The current stack becomes a copy of rightHandSide
and a const reference to it is returned.
------------------------------------------------------------------------*/
bool empty() const;
/*------------------------------------------------------------------------
Check if stack is empty.
Precondition: None
Postcondition: Returns true if stack is empty and false otherwise.
-----------------------------------------------------------------------*/
void push(const StackElement & value);
/*------------------------------------------------------------------------
Add a value to a stack.
Precondition: value is to be added to this stack
Postcondition: value is added at top of stack provided there is space;
otherwise, a stack-full message is displayed and execution is
terminated.
-----------------------------------------------------------------------*/
void display(ostream & out) const;
/*------------------------------------------------------------------------
Display values stored in the stack.
Precondition: ostream out is open.
Postcondition: Stack's contents, from top down, have been output to out.
-----------------------------------------------------------------------*/
StackElement top() const;
/*------------------------------------------------------------------------
Retrieve value at top of stack (if any).
Precondition: Stack is nonempty
Postcondition: Value at top of stack is returned, unless the stack is
empty; in that case, an error message is displayed and a "garbage
value" is returned.
-----------------------------------------------------------------------*/
void pop();
/*------------------------------------------------------------------------
Remove value at top of stack (if any).
Precondition: Stack is nonempty.
Postcondition: Value at top of stack has been removed, unless the stack
is empty; in that case, an error message is displayed and
execution allowed to proceed.
-----------------------------------------------------------------------*/
private:
/*** Node class ***/
class Node
{
public:
StackElement data;
Node * next;
//--- Node constructor
Node(StackElement value, Node * link = 0)
/*-------------------------------------------------------------------
Precondition: None.
Postcondition: A Node has been constructed with value in its data
part and its next part set to link (default 0).
-------------------------------------------------------------------*/
: data(value), next(link)
{}
};
typedef Node * NodePointer;
/***** Data Members *****/
NodePointer myTop; // pointer to top of stack
}; // end of class declaration
#endif
Explanation / Answer
//other stack files remian same, given main.cpp file
#include"LStack.h"
int prime(int *n, int p);
int main()
{
Stack s;
int n,count;
int original;
cout << "Enter the number for which prime factorisation required: ";
cin >> n;
//store prime number
original = n;
//check for smallest prime factors how many
count = prime(&n, 2);
//push number of times 2 factor in number n
for (int i = 0; i < count; i++)
{
s.push(2);
}
//push number of times p (any prime number ) factor in number n
for (int i = 3; i <= n; i = i + 2)
{
count = prime(&n, i);
//push number of times
for (int j = 0; j < count; j++)
{
s.push(i);
}
}
cout << "The prime factorization of number " << original << " : ";
while (!s.empty())
{
cout << s.top();
s.pop();
if (!s.empty())
cout << "*";
}
cout << endl;
}
int prime(int *n,int p)
{
int count = 0;
while (*n % p == 0)
{
count++;
*n /= p;
}
return count;
}
-------------------------------------------------------------------------------------------------------------------
//output
Enter the number for which prime factorisation required: 3960
The prime factorization of number 3960 : 11*5*3*3*2*2*2