CODEWITHSUNDEEP
javaprime-factoringexponent
astrocat1997
astrocat1997

Reputation: 187

Basic Prime Factorization with Exponents in Java

The Problem: Any positive integer can be expressed as a unique product of prime numbers, also know as its prime factorization. For example: 60 = 2^2 * 3 * 5

Write a program to compute the prime factorization of a positive integer.

Input: A single integer, n, where n ≥ 2.

Output: A string with the format: “p^a * q^b * ...”, where p and q are primes, and a and b are exponents. If an exponent is 1, then it should be omitted.

I've got everything else down, I just need to find a way to put it into “p^a * q^b * ...” form.

Here is my code: 

import java.util.Scanner;

public class PrimeFactorization {
public static void main(String[] args) {

     // Input: A single integer, n, where n is greater than or equal to 2.

     System.out.println("Please input an integer greater than or equal to two!");
     System.out.println("This number will be factored.");
     Scanner inputNum = new Scanner(System.in);
     int toBFactored = inputNum.nextInt();

     // If the input does not fit the requirements, ask again for an input.

     while (toBFactored < 2) {
          System.out.println("Please input an integer greater than or equal to two.");
          toBFactored = inputNum.nextInt();
     }

     // Output: A string with the format: "p^a * q^b * ...", where p and q are
     // primes, and a and b are exponents. 
     // Decide first if a number (testNum) is prime.

     int primedecider = 0;
     for (int testNum = 2; testNum < toBFactored; testNum ++) {
          for (int factor = 2; factor < testNum; factor ++) {
               if (testNum % factor != 0 || testNum == 2) {
                    // Do nothing if prime.
               } else {
                    primedecider += 1;
                    // Add if composite.
               }
          }

          // If testNum is prime, if primedecider = 0, test if testNum divides
          // evenly into toBFactored.

          while (primedecider == 0 && toBFactored % testNum == 0 {
               System.out.print(testNum + " ");
               toBFactored /= testNum;
          }
     }
     System.out.print(toBFactored);

     inputNum.close();
}
}

My output for 120 is "2 2 2 3 5". How do I make it into 2^3 * 3 * 5?

Upvotes: 1

Views: 1259

Answers (1)

janos
janos

Reputation: 124656

If instead of printing the factors with System.out.println, if you put them in a list, then these functions will format them in the way you described. This is of course just one of the many ways of doing this.

private String formatFactors(List<Integer> factors) {
    StringBuilder builder = new StringBuilder();

    int prev = factors.get(0);
    int power = 1;
    int factor = prev;

    for (int i = 1; i < factors.size(); ++i) {
        factor = factors.get(i);
        if (factor == prev) {
            ++power;
        } else {
            appendFactor(builder, prev, power);
            prev = factor;
            power = 1;
        }
    }
    appendFactor(builder, factor, power);

    return builder.substring(3);
}

private void appendFactor(StringBuilder builder, int factor, int power) {
    builder.append(" * ").append(factor);
    if (power > 1) {
        builder.append("^").append(power);
    }
}

Upvotes: 1

Related Questions