Prime Factorization в Java

Question

Я работаю над основной программой факторизации на Java, которая отображает все простые факторы числа, даже если они повторяются.И у меня есть это:

public static void factors(int a)
{
    int c=1;
    for(int i = 1; i <= a;i++)
    {
        if(a%i == 0)
        {
            for(int k = 2; k < i; k++)
            {
                if(i%k == 0)
                {
                    c = 1;
                    break;
                }
                else
                {
                    c = 0;
                }
            }
            if(c == 0 || i == 2)
            {
                System.out.print(i+ ", ");
            }
        }
    }
}

Мне нужно учитывать повторяющиеся факторы (как в 2, 2, 2 для 8).Как я могу сделать это без полной реструктуризации?

Answer 1

Я думаю, вы должны начать все сначала и построить алгоритм из этого простого описания:

• Подготовьте List<Integer> простых чисел, которые меньше или равны 2 ^ 16
• Пробежаться по этому списку от низкого к высокому, пробуя каждое простое число по очереди в качестве делителя-кандидата
• Каждый раз, когда вы сталкиваетесь с рабочим делителем, непрерывно делите его, пока вы больше не сможете делить число на него; затем перейдите к следующему простому
• Как только вы достигнете конца списка простых чисел, оставшееся число также должно быть напечатано, если оно не равно 1.

Поиск списка простых чисел сам по себе является забавной проблемой. Дейкстра написал замечательную главу об этом еще в 1972 году. Эта статья имеет реализацию на C ++ и очень приятное обсуждение.

Answer 2

(1) if(c == 0 || i == 2) неверно, также будет напечатано 2 для a == 5.

(2) Чтобы выполнить то, что вы просите, без изменения кода (*) -Вы должны посчитать, сколько раз каждый главный фактор делится на число.Это можно сделать, просто добавив новый цикл перед оператором печати [псевдокод]:

boolean b = true;
int k = 1;
while (b) { 
  if (a % (int) Math.pow(i, k+1) == 0) k++;
  else b = false;
}

в конце этого цикла, k обозначает, сколько раз i является простым фактором a.

(*) Примечание. Хотя этот подход должен сработать, я бы все же согласился с предложением @KerrekSB и переработал его.

Answer 3

У вас может быть другая коллекция, которая поддерживает факторы и их количество и, наконец, может учитывать повторяющиеся факторы.Я бы выбрал карту с подсчетами.