### Need Help Coding This In C++

Given This, code, for the stack header and implementation, have to create this program.

For a given integer n (n>1), the smallest integer d (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 quoient of n divided by d, repeating this until n becomes 1. Write a program that queries the user for an integer >1 and computes the prime factorization of n in this manner, but displays the prime factors in descending order.
For example if n is 3960 your program would produce (can be displayed horizontally or vertically)
11 5 3 3 2 2 2

Here is the stack.h and stack.cpp we need a main.cpp to make it work.
Stack.cpp
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465`` ``````/*-- Stack.cpp------------------------------------------------------------- This file implements Stack member functions. --------------------------------------------------------------------------*/ #include #include using namespace std; #include "Stack.h" //--- Definition of Stack constructor Stack::Stack() : myTop(-1) {} //--- Definition of empty() bool Stack::empty() const { return (myTop == -1); } //--- Definition of push() void Stack::push(const StackElement & value) { if (myTop < STACK_CAPACITY - 1) //Preserve stack invariant { ++myTop; myArray[myTop] = value; } else { cerr << "*** Stack full -- can't add new value ***\n" "Must increase value of STACK_CAPACITY in Stack.h\n"; exit(1); } } //--- Definition of display() void Stack::display(ostream & out) const { for (int i = myTop; i >= 0; i--) out << myArray[i] << endl; } //--- Definition of top() StackElement Stack::top() const { if ( !empty() ) return (myArray[myTop]); else { cerr << "*** Stack is empty -- returning garbage value ***\n"; StackElement garbage; return garbage; } } //--- Definition of pop() void Stack::pop() { if ( !empty() ) myTop--; else cerr << "*** Stack is empty -- can't remove a value ***\n"; }``````

Stack.h
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192`` ``````/*-- Stack.h --------------------------------------------------------------- This header file defines a Stack data type. Basic operations: constructor: Constructs an empty stack empty: Checks if a stack is empty push: Modifies a stack by adding a value at the top top: Retrieves the top stack value; leaves stack unchanged pop: Modifies stack by removing the value at the top display: Displays all the stack elements Class Invariant: 1. The stack elements (if any) are stored in positions 0, 1, . . ., myTop of myArray. 2. -1 <= myTop < STACK_CAPACITY --------------------------------------------------------------------------*/ #include #ifndef STACK #define STACK const int STACK_CAPACITY = 128; typedef int StackElement; class Stack { public: /***** Function Members *****/ /***** Constructor *****/ Stack(); /*------------------------------------------------------------------------ Construct a Stack object. Precondition: None. Postcondition: An empty Stack object has been constructed (myTop is initialized to -1 and myArray is an array with STACK_CAPACITY elements of type StackElement). -----------------------------------------------------------------------*/ 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: /***** Data Members *****/ StackElement myArray[STACK_CAPACITY]; int myTop; }; // end of class declaration #endif ``````
Last edited on
if we find d
^^^ this is the intractable part that makes prime factorization the backbone of modern encryption. Its extremely difficult to find d for larger numbers. If you are only working with smaller numbers you can do it of course.

all the stack appears to be there for is to reverse the output (???). Which is silly, you can do that much, much easier other ways, but you may as well use what they handed you.

can you get the prime factors of a number, or is that what you do not know how to do, or what is your question exactly (it looks like you just handed us the assignment untouched, I am not sure what you did here and where you got stuck).
d=2
n=3960
Can d divide 3960? yes
n=1980
Can d divide 1980? yes
n=990
Can d divide 990? yes
n=495
Can d divide 495? no
d=3
Can d divide 495? yes
n=165
Can d divide 165? yes
n=55
Can d divide 55? no
d=4
Can d divide 55? no
d=5
Can d divide 55? yes
n=11
Can d divide 11? no
d=6
Can d divide 11? no
d=7
...
d=11
Can d divide 11? yes
n=1
Complete.

Each iteration of that "loop" does one of two possible things. On every successful divide the d must be stored to the stack.

Afterwards, you must print the content of the stack. Will the results be in required order?
Last edited on
Well simply, possibly consider:

 ``123456789101112131415`` ``````#include #include #include #include int main() { auto n {3960U}; std::vector facts; for (auto d {2U}; n > 1; ++d) for (; n % d == 0; n /= d) facts.push_back(d); std::copy(facts.crbegin(), facts.crend(), std::ostream_iterator(std::cout, " ")); }``````

 ``` 11 5 3 3 2 2 2 ```

Doh! Where I saw first "while fails" iteration (and then "either or" repeat), you have "while succeeds". So many ways. :)
Last edited on
Well, this sort of uses a "stack":

 ``123456789101112131415161718192021`` ``````#include void factor( int n, int test = 2 ) { if ( n <= 1 ) return; if ( n % test ) { factor( n, test + 1 ); } else { factor( n / test, test ); std::cout << test << " "; } } int main() { int n = 3960; factor( n ); }``````
Last edited on
Nice, but we gotta use the stack.h to do this, so when the user enters 3960 its suppose to show
11 5 3 3 2 2 2
suppose to be like this, but is there a better to do it?
#include <iostream>

using namespace std;

#include "stack.h"

int main(void)
{
int userInt = 0, // user provided int
i = 0, // counter
q = 0, // quotient
stackCount = 0; // number of values in stack

int primeArray [] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; //array of prime numbers for calculations

// 1. Explain the purpose of the program
cout << "This program will calculate the prime factor of an integer provided by the user of the program." << endl;

// 2. Ask user for an int
cout << "Please enter an integer that is greater than 1: ";

// 3. Store int to memory
cin >> userInt;

// 4. Validate the user's entry as being greater than 1, terminate program if less than 2.
if(userInt <2)
{
cout << "\n\nThis program will not work with integers of less than 1." << endl;
}

// 5. If the user's int is greater than 1, run routine to calculate prime factorization.
else if (userInt > 1)
{

// 6. Create stack primeStack
Stack primeStack;

// 7. divide user provides int by prime numbers, looking for a mod of 0. Upon calculation, push divisor to stack
for(i=0; userInt>1; i++)
{
if(userInt % primeArray[i]==0)
{
q = userInt / primeArray[i];

primeStack.push(primeArray[i]); // push prime factor to the stack
stackCount++; // counting values added to the stack
i = -1; // resetting counter to -1

// 8. replace userInt with q to allow calculation to run again
userInt = q;

}
}

// 9. Displaying stack
cout << "\nYour prime factors are:" << endl;

for(i=stackCount; i>0; i-- )
{
cout << primeStack.top();
primeStack.pop();
if(i>1)
{
cout << " * ";
}
}
}
cout << "\n\nProgram terminating." << endl;
return 0;
}
Well change my L12 to push to the provided stack (.push())

Then my L14 is changed to display the stack. Use .top() then .pop() while !empty()
First, posting with code tags and indentation makes code easier to read. See https://www.cplusplus.com/articles/jEywvCM9/

 ``123456789101112`` ``````// 9. Displaying stack cout << "\nYour prime factors are:" << endl; for ( i=stackCount; i>0; i-- ) { cout << primeStack.top(); primeStack.pop(); if ( i>1 ) { cout << " * "; } }``````

Did the instructions require "` * `" between prime factors? Details, details, details.

Now, look at this detail of the class Stack:
 ``1234567891011121314`` ``````class Stack { public: /***** Function Members *****/ bool empty() const; /*------------------------------------------------------------------------ Check if stack is empty. Precondition: None Postcondition: Returns true if stack is empty and false otherwise. -----------------------------------------------------------------------*/ // ... };``````

Yes, the Stack can tell if it is empty. It does keep track of how many elements it has currently. Your `stackCount` is redundant. You both do unnecessary work by having it and make yourself prone to errors. What if stackCount is wrong due to some mistake?
Topic archived. No new replies allowed.