Imprimer toutes les combinaisons uniques de facteurs d’un nombre donné

Essayez cette approche récursive qui prend également 2 entrées supplémentaires, à savoir une chaîne pour reporter la valeur actuelle de i in for loop pour effectuer une réduction ultérieure, ainsi qu’un temp int pour savoir quand ne pas imprimer les inversions en double, à savoir 8 * 3 et 3 *. 8

 public static void printFactors(int number, Ssortingng 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); } } } } 

Et appelez cette méthode en utilisant printFactors (12, '', 12)
Faites-moi savoir si vous trouvez des failles dans cette approche. Merci!

1) Si i < num et i > num/2 , alors num % i == num - i . (Facile à prouver.) Ainsi, votre boucle for vérifiera inutilement tous les entiers supérieurs à num/2 et l'instruction if ne réussira qu'une fois, avec temp == 2 . Je ne pense pas que c'est ce que tu voulais.

2) Dans ce problème, la récursivité peut nécessiter beaucoup de réponses. Mais vous n'imprimez qu'une seule fois temp * . Donc, la sortie aura l'air un peu bizarre.

3) isprime est inutile. num est toujours un facteur légitime, qu’il soit ou non premier, à condition de suivre le point ci-dessous.

4) Enfin, vous devez trouver un moyen d’éviter d’imprimer plusieurs fois la même factorisation. La solution simple consiste à ne produire que des factorisations dans lesquelles les facteurs n'augmentent pas de façon monotone (comme dans votre exemple). Pour ce faire, la récursivité doit produire des factorisations avec un facteur maximum (qui serait le facteur précédemment découvert). La fonction récursive doit donc avoir (au moins) deux arguments: le nombre à factoriser et le facteur maximal autorisé. (Vous devez également traiter le problème que j'ai noté au point 4.)

Le code Python suivant résout (je crois) le problème, mais il divise encore un certain nombre de divisions inutiles. À la différence du style python, chaque factorisation est imprimée au lieu d'agir en tant que générateur, car elle sera plus facile à traduire en 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 sortingal_factor in range(max_factor, 1, -1): remnant = number / sortingal_factor if remnant * sortingal_factor == number: factors(remnant, accum + [sortingal_factor,]) 

Il est possible d'optimiser la déclaration for . Par exemple, une fois que vous calculez le remnant , vous savez que le prochain remnant doit être au moins supérieur, vous pouvez donc ignorer un sortingal_factor valeurs sortingal_factor lorsque le remnant est petit.

Ce code trouve tous les facteurs d’un nombre et les sortinge (localement et globalement):

 public class PrimeFactors { final SortedSet< List< Integer >> _solutions = new TreeSet<>( new Comparator>(){ @Override public int compare( List left, List 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( Ssortingng[] 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 ); } } } 

Les sorties:

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

Voici ma solution basée sur les idées de @ 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) # -> [] 

J’ai une solution sans récursion ni sorting ni stacks en C / C ++.

 #include  #include  // 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 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; } 

Et la sortie est comme ça:

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

 vector GetAllFactors(unsigned int number) { vector factors; for (int i = 2; i <= number; i++) { if (number % i == 0) { factors.push_back(i); } } return factors; } void DoCombinationWithRepetitionFactors(vector allFactors, unsigned currentProduct, unsigned targetProduct, vector 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(); } } } 

 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<2) cout< done; for(i=2; i 

Je suis venu avec cela, semble facile à lire et à comprendre. J’espère que cela aide!

 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