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

Ответ 1

Попробуйте этот рекурсивный подход, который также принимает еще 2 ввода, а именно строку для переноса текущего значения цикла я in 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)
Дайте мне знать, если вы обнаружите недостатки в этом подходе. Благодарю!

Ответ 2

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 невелик.

Ответ 3

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

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]

Ответ 4

Вот мое решение, основанное на идеях @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) # -> []

Ответ 5

У меня есть решение без рекурсии или сортировки или стеков в 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,

Ответ 6

vector<unsigned int> GetAllFactors(unsigned int number)
{
    vector<unsigned int> factors;

    for (int i = 2; i <= number; i++)
    {
        if (number % i == 0)
        {
            factors.push_back(i);
        }
    }

    return factors;
}

void DoCombinationWithRepetitionFactors(vector<unsigned int> allFactors, unsigned currentProduct, unsigned targetProduct, vector<unsigned int> currentFactorSet, unsigned currentFactorIndex)
{
    if (currentProduct == targetProduct)
    {
        for (auto a : currentFactorSet)
        {
            cout << a << " , ";
        }

        cout << endl;

        return;
    }


    for (int i = currentFactorIndex; i < allFactors.size(); i++)
    {
        if (currentProduct * allFactors[i] <= targetProduct)
        {
            currentFactorSet.push_back(allFactors[i]);
            DoCombinationWithRepetitionFactors(allFactors, currentProduct * allFactors[i], targetProduct, currentFactorSet, i);
            currentFactorSet.pop_back();
        }
    }
}

Ответ 7

bool isprime(int n){
for(int i=2; i<=sqrt(n); i++)
    if(n%i==0)
        return false;
return true;
}

void printprime(int n){

int i,j,y=n;

while(y%2==0){
    cout<<"2 * ";
    y/=2;
}

for(i=3; i<=sqrt(y); i+=2){
    while(y%i==0){
        cout<<i<<" * ";
        y/=i;
    }
}

if(y>2)
    cout<<y;
}

void allfacs(int n){

int i;
unordered_set<int> done;

for(i=2; i<sqrt(n); i++){
    if(n%i==0){
        cout<<i<<" * "<<n/i<<endl;

        if(!isprime(i) && done.find(i) == done.end()){
            done.insert(i);
            printprime(i);
            cout<<n/i<<endl;
        }
        if(!isprime(n/i) && done.find(n/i) == done.end()){
            done.insert(n/i);
            cout<<i<< " * ";
            printprime(n/i);
            cout<<endl;
        }
    }
}
}

Ответ 8

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

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

Ответ 9

#include<bits/stdc++.h>
using namespace std;
int n;
// prod = current product of factors in combination vector
// curr = current factor
void fun(int curr, int prod, vector<int> combination )
{
    if(prod==n)
    {
        for(int j=0; j<combination.size(); j++)
        {
            cout<<combination[j]<<" ";
        }
        cout<<endl; 
        return;
    }

    for(int i=curr; i<n; i++)
    {
        if(i*prod>n) break;
        if(n%i==0)
        {
            combination.push_back(i);
            fun(i, i*prod, combination);
            combination.resize(combination.size()-1);
        }
    }
}

int main()
{
    cin>>n;
    vector<int> combination;
    fun(2, 1, combination);
    cout<<1<<" "<<n;
    return 0;
}