问题打印给定数字的所有因素的唯一组合

打印正整数因子的所有唯一组合的最有效算法是什么。例如，如果给定的数字是24，那么输出应该是

24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2

这里注意到当打印6 * 4时，不打印4 * 6。所以基本上这是一个在不考虑顺序的情况下获取唯一子集的问题（一种查看问题的方法）。但目标是拥有一个运行速度最快的函数，因此将因子存储在数据结构中以进行进一步操作可能会消耗更多时间。我已经尝试了我的算法并粘贴了下面的代码，但它似乎没有给我想要的结果，我在递归调用中犯了一些错误。你能帮我找出一个有效的方法吗？

public static void printfact(int num){
        int temp=0;
        for(int i=num-1;i>=num/2;i--){
            if(num % i == 0){
                temp = num/i;
                System.out.println(temp + " * " + i);
                if(isprime(i)==false){
                    System.out.print(temp + " * ");
                    printfact(i);
                }
            }
        }
}

10955

2018-02-27 21:07

起源

感谢编辑建议Sanjeev的问题 - crazyim5

我认为你需要： en.wikipedia.org/wiki/... 找到所有因素后。 - Ray Tayek

6和4都不是24（或任何其他数字）的主要因素，因为它们不是......好的。 - Philip

@Aubin这是正确的标题，它不是关于印刷素因而是所有因素的组合。看看我给出的例子。 - crazyim5

答案:

尝试这种递归方法，它还需要另外2个输入，即一个字符串，用于在for循环中执行i的当前值以执行后续缩减，还使用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）
如果你发现这种方法存在缺陷，请告诉我。谢谢！

2018-02-28 01:24

这个答案会忽略OP所追求的1 * n答案。除此之外，我认为它确实抓住了一切。 - demongolem

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 是小。

2018-02-27 21:30

确切地说，我不确定是否可以使用辅助字符串参数传递函数，该参数在递归减少较大元素之前传承先前要打印的因子（例如，如果数字是40然后是10 * 4然后减少两者10和4分为5 * 2 * 2 * 2等。）。但是我们将如何第一次调用该函数。我很难想象它。 - crazyim5

不，你不需要减少10和4.第一个因素 5 应该稍后出现。所以你应该生产 10*4 和 10*2*2 接着 8*5 接着 5*4*2 和 5*2*2*2。（那是在其他因素之后， 40 和 20*2当然。）所以问题是如何有效地决定递归中哪些是合理的第一因素，而不进行大量不必要的模数运算。 - rici

是的你是对的，但如何递归设备。你能提供一个示例代码吗？ - crazyim5

@ crazyim5：添加了一些python代码，你可以考虑伪代码。 - rici

谢谢里奇，我修改了一点，并由我自己回答。让我知道你的想法。 - crazyim5

此代码查找数字的所有因子，对它们进行排序（本地和全局）：

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]

2018-02-27 21:34

谢谢你的解决方案。是的，这几乎是我第一次做的，但我们需要消除重复的组合。 - crazyim5

不生成重复项比在事后消除重复项更有效。正如我所说，关键是始终产生单调非增长序列;这并不难。 - rici

我改进了算法，在遍历分解时消除了已经走过的路径。 - Aubin

这是我基于@ 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) # -> []

2017-12-25 20:33

我有一个没有递归或排序或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,

2018-01-16 20:20

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

2017-07-12 02:21

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

2017-12-18 22:23

我想出了这个，似乎很容易阅读和理解。希望能帮助到你！

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

2018-01-11 23:14

问题 打印给定数字的所有因素的唯一组合

答案:

热门问题

问题打印给定数字的所有因素的唯一组合