Вывести все уникальные комбинации факторов заданного числа

Попробуйте этот рекурсивный подход, который также принимает еще 2 входа, а именно строку для переноса текущего значения i в цикл for для выполнения последующего сокращения, а также temp int, чтобы знать, когда не печатать повторяющиеся изменения, т. Е. 8 * 3 и 3 * 8.

public static void printFactors(int number, String parentFactors, int parentVal) {
    int newVal = parentVal;
    for (int i = number - 1; i >= 2; i--) {

        if (number % i == 0) {
            if (newVal > i) {
                newVal = i;
            }
            if (number / i <= parentVal && i <= parentVal
                    && number / i <= i) {
                System.out.println(parentFactors + i + "*" + number / i);
                newVal = number / i;
            }

            if (i <= parentVal) {
                printFactors(number / i, parentFactors + i + "*", newVal);
            }
        }

    }

}

И вызовите этот метод, используя printFactors(12,'',12)
Сообщите мне, если вы обнаружите недостатки в этом подходе. Спасибо!

1) Если i < num и i > num/2, то num % i == num - i. (Легко доказать.) Таким образом, ваш цикл for будет бессмысленно проверять все целые числа больше num/2, а оператор if будет успешным только один раз, с temp == 2. Не думаю, что ты этого хотел.

2) Если вы исправили это, рекурсия может потребовать много ответов. Но вы печатаете temp * только один раз. Таким образом, вывод будет выглядеть немного странно.

3) isprime не нужен. num всегда является законным фактором, независимо от того, является ли он простым, при условии, что вы следуете приведенному ниже пункту.

4) Наконец, вам нужно выяснить, как избежать многократного вывода одной и той же факторизации. Простое решение состоит в том, чтобы производить факторизации только там, где факторы монотонно не возрастают (как в вашем примере). Чтобы сделать это, рекурсия должна производить факторизации с некоторым максимальным фактором (который будет ранее обнаруженным фактором). Таким образом, рекурсивная функция должна иметь (по крайней мере) два аргумента: число для факторизации и максимально допустимый фактор. (Вам также необходимо решить проблему, которую я отметил в пункте 4.)

Следующий код Python действительно (я полагаю) решает проблему, но он все же делает довольно много ненужных делений. В отличие от стиля Python, он печатает каждую факторизацию вместо того, чтобы действовать как генератор, потому что это будет легче перевести на Java.

# Uses the last value in accum as the maximum factor; a cleaner solution
# would have been to pass max_factor as an argument.
def factors(number, accum=[]):
  if number == 1:
    print '*'.join(map(str, accum))
  else:
    if accum:
      max_factor = min(accum[-1], number)
    else:
      max_factor = number
    for trial_factor in range(max_factor, 1, -1):
      remnant = number / trial_factor
      if remnant * trial_factor == number:
        factors(remnant, accum + [trial_factor,])

Оператор for можно оптимизировать. Например, когда вы вычисляете remnant, вы знаете, что следующее remnant должно быть как минимум на единицу больше, поэтому вы можете пропустить группу значений trial_factor, когда remnant мало.

Этот код находит все факторы числа, сортирует их (локально и глобально):

public class PrimeFactors {

   final SortedSet< List< Integer >> _solutions = new TreeSet<>(
      new Comparator<List<Integer>>(){
         @Override
         public int compare( List<Integer> left, List<Integer> right ) {
            int count = Math.min( left.size(), right.size());
            for( int i = 0; i < count; ++i ) {
               if( left.get(i) < right.get(i)) {
                  return -1;
               }
               if( left.get(i) > right.get(i)) {
                  return +1;
               }
             }
            return left.size() - right.size();
         }});

   public SortedSet< List< Integer >> getPrimes( int num ) {
      _solutions.clear();
      getPrimes( num, new LinkedList< Integer >());
      return _solutions;
   }

   private void getPrimes( int num, List< Integer > solution ) {
      for( int i = num - 1; i > 1; --i ) {
         if(( num % i ) == 0 ) {
            int temp = num / i;
            List< Integer > s = new LinkedList<>();
            s.addAll( solution );
            s.add( temp );
            s.add( i );
            Collections.sort( s );
            if( _solutions.add( s )) { // if not already found
               s = new LinkedList<>();
               s.addAll( solution );
               s.add( temp );
               getPrimes( i, s );
             }
         }
      }
   }
   public static void main( String[] args ) {
      SortedSet< List< Integer >> solutions =
         new PrimeFactors().getPrimes( 24 );
      System.out.println( "Primes of 24 are:" );
      for( List< Integer > l : solutions ) {
         System.out.println( l );
      }
   }
}

Выходы:

Primes of 24 are:
[2, 2, 2, 3]
[2, 2, 6]
[2, 3, 4]
[2, 12]
[3, 8]
[4, 6]

У меня есть решение без рекурсии, сортировки или стеков на C/C++.

#include <vector>
#include <iostream>

// For each n, for each i = n-1 to 2, try prod = prod*i, if prod < N.

int
g(int N, int n, int k)
{
        int i = k;
        int prod = n;
        std::vector<int> myvec;

        myvec.push_back(n);
        while (i > 1) {
                if (prod * i == N) {
                        prod = prod*i;
                        myvec.push_back(i);
                        for (auto it = myvec.begin();
                                it != myvec.end(); it++) {
                                std::cout << *it << ",";
                        }
                        std::cout << std::endl;
                        return i;
                } else if (prod * i < N) {
                        prod = prod*i;
                        myvec.push_back(i);
                } else { i--;}
        }

        return k;
}

void
f(int N)
{
        for (int i = 2; i <= N/2; i++) {
                int x = g(N, i, i-1);
                // Extract all possible factors from this point
                while (x > 0) {
                        x = g(N, i, x-1);
                }
        }
}

int
main()
{
        f(24);

        return 0;
}

И вывод такой:

$ ./a.out
    3,2,2,2,
    4,3,2,
    6,4,
    6,2,2,
    8,3,
    12,2,

Вот мое решение, основанное на идеях @rici.

def factors(number, max_factor=sys.maxint):
    result = []

    factor = min(number / 2, max_factor)
    while factor >= 2:
        if number % factor == 0:
            divisor = number / factor

            if divisor <= factor and divisor <= max_factor:
                result.append([factor, divisor])

            result.extend([factor] + item for item in factors(divisor, factor))

        factor -= 1

    return result

print factors(12) # -> [[6, 2], [4, 3], [3, 2, 2]]
print factors(24) # -> [[12, 2], [8, 3], [6, 4], [6, 2, 2], [4, 3, 2], [3, 2, 2, 2]]
print factors(157) # -> []

Я придумал это, кажется, легко читать и понимать. Надеюсь, поможет!

def getFactors(num):

    results = []

    if num == 1 or 0:
        return [num]

    for i in range(num/2, 1, -1):

        if (num % i == 0):
            divisor = num / i

            if(divisor <= i):
                results.append([i, divisor])

            innerResults = getFactors(divisor)

            for innerResult in innerResults:
                if innerResult[0] <= i:
                    results.append([i] + innerResult)

    return results