Базовая простая факторизация с показателями в Java

Question

Проблема: любое положительное целое число может быть выражено как уникальный продукт простых чисел, также известный как его первичная факторизация. Например: 60 = 2^2 * 3 * 5

Напишите программу для вычисления простой факторизации натурального числа.

Входные данные: одно целое число n, где n ≥ 2.

Вывод: строка в формате: "p^a * q^b * ...", где p и q - простые числа, а a и b - показатели степени. Если показатель степени равен 1, то его следует опустить.

У меня есть все остальное, мне просто нужно найти способ поместить его в форму "p^a * q^b * ...".

Вот мой код:

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();
}
}

Мой вывод на 120 "2 2 2 3 5". Как мне сделать это в 2^3 * 3 * 5?

Answer 1

Если вместо того, чтобы печатать факторы с System.out.printlnЕсли вы поместите их в список, то эти функции отформатируют их так, как вы описали. Это, конечно, только один из многих способов сделать это.

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);
    }
}