C++

Forum

 
Need Help Coding This In C++

MichaelWanneb (26)
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
/*-- Stack.cpp-------------------------------------------------------------
              This file implements Stack member functions.
--------------------------------------------------------------------------*/

#include <iostream>
#include <cstdlib>
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
/*-- 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 <iostream>

#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
jonnin (11350)
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).
keskiverto (10368)
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
seeplus (6479)
Well simply, possibly consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
	auto n {3960U};
	std::vector<decltype(n)> 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<decltype(n)>(std::cout, " "));
}



11 5 3 3 2 2 2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <iostream>

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
MichaelWanneb (26)
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
MichaelWanneb (26)
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;
}
seeplus (6479)
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()
keskiverto (10368)
First, posting with code tags and indentation makes code easier to read. See https://www.cplusplus.com/articles/jEywvCM9/

1
2
3
4
5
6
7
8
9
10
11
12
 
// 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
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.