For a given integer n > 1, the smallest integer d > 1 that divides n is a prime

Question

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 java program that uses a stack to print the prime factors of a positive integer in descending order. For example, for n = 3960, your program should produce 11*5*3*3*2*2*2 Show the ArrayStackADT interface Create the ArrayStackDataStrucClass with the following methods: default constructor, overloaded constructor, copy constructor, initializeStack, isEmptyStack, isFullStack, push, peek, void pop Create the PrimeFactorizationDemoClass: instantiate an ArrayStackDataStrucClass object with 50 elements. Use a try- catch block in the main() using pushes/pops. Exception classes: StackException, StackUnderflowException, StackOverflowException Show the 4 outputs for the following: 3, 960 1, 234 222, 222 13, 780

Explanation / Answer

Q1. Write a java program that uses a stack to print the prime factors of a positive integer in decending order.

Ans. Below program is a fully functional program in which n is the number for which prime factors are found in ascending order and stored in a stack. Since a stack is a LIFO (Last In First Out) algorithm, when we pop out the prime factors from stack, we find the output to be in DESCENDING order. The below program, when run, verifies the same output for the input shown in the example (3960).

public class PrimeFactorStack{
   private int max;
   private long[] pfsArray;
   private int top;
   public PrimeFactorStack(int s) {
      max = s;
      pfsArray = new long[max];
      top = -1;
   }
   public void push(long j) {
      pfsArray[++top] = j;
   }
   public long pop() {
      return pfsArray[top--];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public static void main(String[] args) {
        int n=3960,i=2;
        PrimeFactorStack pfs = new PrimeFactorStack(n/2);
            while(n!=1){
                while(n%i==0){
                    pfs.push(i);
                    n /= i;
                }
                i++;
            }
        while (!pfs.isEmpty()) {
            long value = pfs.pop();
            System.out.print(value+" ");
            System.out.print(" ");
        }
        System.out.println("");
    }
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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