The problem to solve is: For a given integer n > 1, the smallest integer d > 1 t

Question

The problem to solve is: 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. For example, for n = 3960, your program should produce 11 * 5 * 3 * 3 * 2 * 2 *2. Requirements: 1. Use linked stack to store the factors. Implement all necessary functions of the stack class. 2. Read input value n from keyboard with proper prompting message. 3. Print prime factors with proper labeling and in descending order connected with " * ", as shown in the previous example.

This is what I currently have:

#include
using namespace std;

class Node {
int data;
Node* next;
public:
Node() {};
void SetData(int aData) { data = aData; };
void SetNext(Node* aNext) { next = aNext; };
int Data() { return data; };
Node* Next() { return next; };
};

class List {
Node *head;
public:
List() { head = NULL; };
           ~List() {}
void Display();
void Append(int data);
void Remove(int data);
};

void List::Display() {
Node *tmp = head;
if ( tmp == NULL ) {
cout << "EMPTY" << endl;
return;
}
   else if ( tmp->Next() == NULL ) {
cout << tmp->Data();
cout << " --> ";
cout << "NULL" << endl;
}
else {
do {
cout << tmp->Data();
cout << " --> ";
tmp = tmp->Next();
} while ( tmp != NULL );
cout << "NULL" << endl;
}
}

void List::Append(int data) {
Node* newNode = new Node();
newNode-> SetData((int)data);
newNode->SetNext(NULL);
Node *tmp = head;
if ( tmp != NULL ) {
while ( tmp->Next() != NULL ) {
tmp = tmp->Next();
}
tmp->SetNext(newNode);
}
else {
head = newNode;
}
}

void List::Remove(int data) {
Node *tmp = head;
if ( tmp == NULL )
return;
else if ( tmp->Next() == NULL ) {
delete tmp;
head = NULL;
}
else
   {
Node *prev = tmp;
do {
if ( tmp->Data() == data ) break;
prev = tmp;
tmp = tmp->Next();
} while ( tmp != NULL );
prev->SetNext(tmp->Next());
delete tmp;
}
}

int main() {
List list;
int n[100], i, size;
char choice;
for(i=1; i<=100; i++){
cout<<"Insert[I] Display[D] Remove[R] ";
cin>>choice;
if (choice=='I'||choice=='i'){
cout<<"Enter the number of nodes: ";
cin>>size;
cout<<"Enter a number to be inserted: ";
for(i=1; i<=size; i++){
cin>>n[i];
list.Append(n[i]);
}
}
if (choice=='D'||choice=='d'){
cout<<"Elements in the list are: ";
list.Display();
}
if (choice=='R'||choice=='r'){
cout<<"Enter a number to be removed: ";
cin>>n[i];
list.Remove(n[i]);
}
}
}

Explanation / Answer

#include <iostream>
using namespace std;

class Node {
int data;
Node* next;
public:
Node() {};
void SetData(int aData) { data = aData; };
void SetNext(Node* aNext) { next = aNext; };
int Data() { return data; };
Node* Next() { return next; };
};

class Stack {
Node *head;
public:
Stack() { head = NULL; };
~Stack() {}

bool Empty();
void Push(int data);
int Pop();
};

bool Stack::Empty() {
return head == NULL;
}

void Stack::Push(int data) {
Node* newNode = new Node();
newNode->SetData((int)data);
newNode->SetNext(head);
head = newNode;
}

int Stack::Pop() {
if (head == NULL)
return 0;
int data = head->Data();
Node* tmp = head;
head = head->Next();
delete tmp;
return data;
}

int main() {
Stack stack;
int n;
cout << "Enter the number n: ";
cin >> n;

int org = n;
int num = 2;

while (num <= org && n > 1)
{
if (n % num == 0)
{
stack.Push(num);
n = n / num;
}
else
{
num++;
}
}

cout << org << " = " << stack.Pop();
while (!stack.Empty())
cout << " * " << stack.Pop();
cout << endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.