Factoriser de grands nombres en triplets

Question

J'ai trouvé des questions similaires mais c'est un peu plus compliqué.

J'ai un grand nombre n (j'ai en fait plus, mais ce n'est pas grave maintenant), (> 40 chiffres), et je veux trouver un * b * c = n triplets. La factorisation première de n est faite. Il n'a pas de grands diviseurs principaux, mais beaucoup de petits diviseurs premiers. La somme de tous les diviseurs premiers (diviseurs multiples inclus) est supérieure à 50.

Je voudrais trouver un * b * c = n triplets, où < = b < = c. Je ne veux pas tous les triplés, parce qu'ils sont trop nombreux. Je cherche des spéciales.

Par exemple:

• le triplet (s) où CA est minime,
• le triplet (s) où c/a minimal,
• celui où a, b et c a la diviseur commun maximal,
• ces conditions combinées.

Ceci peut être un peu plus facile à résoudre si l'on sait que n = k! (Factoriel). La résolution pourrait conduire à une méthode générale. Le calcul de tous ces triplets avec force brute n'est pas une option en raison de la taille de n, j'ai donc besoin d'un bon algorithme ou d'outils spéciaux pour m'aider à implémenter une solution pour cela.

Désolé pour mon mauvais anglais,

Merci pour les réponses!

Answer 1

je pourrais avoir la solution, mais je n'ai pas le temps de mettre en œuvre aujourd'hui. Je l'écris, alors peut-être que quelqu'un sera d'accord avec moi ou repèrera le point faible de mon algorithme. Voyons donc le premier ou le second cas, où c/a ou c-a devrait être minimal. 1: Dans un premier temps, je divise les facteurs premiers du groupe n en 3 avec un algorithme glouton. Je vais avoir une initiale a, b et c et ils ne seront pas très loin l'un de l'autre. Les facteurs premiers seront stockés dans 3 tableaux: a_pf, b_pf, c_pf. 2: Dans l'étape suivante, je calcule tous les facteurs possibles pour a, b et c, je les stocke dans des tableaux différents, puis je commande ces tableaux. Ceux-ci seront a_all, b_all et c_all. 3: Je calcule q = max (a, b, c)/min (a, b, c).(maintenant nous pouvons dire que a est le plus petit, c est le plus grand nombre)

4: Je recherche a_all et c_all pour les nombres sur cette condition: c_all [i]/a_all [j] < q. Quand je le trouve, je change les facteurs premiers de ces valeurs dans a_pf et c_pf. Avec cette méthode, le plus grand et le plus petit membre du triplet se rapprocheront l'un de l'autre. Je répète les étapes 2-3-4, jusqu'à ce que je le puisse. Je pense que cela se terminera après un nombre fini d'étapes.

Puisque les membres du triolet sont plus petits que le n original, j'espère que cette solution me donnera le triplet correct au plus en quelques minutes.

Answer 2

Vous pouvez le faire avec un simple, O(|D|^2) algorithmes, où D est une liste ordonnée de tous les numéros divisant n, que vous avez déjà.

Notez que vous suffit de trouver a,b, parce c=n/(a*b), de sorte que les problèmes se résume à trouver toutes les paires (a,b) dans D de sorte que a<b et n/(a*b) ∈ D.

pseudocode:

result = empty_list 
for (int i=0; i<D.size-1, i++) {   // O(|D|) 
    for (j=i+1; j<D.size, j++) {   // O(|D|) 
     a, b = D[i], D[j] 
     c = n/(a*b) 
     if (D.contains(c) && c>b) {  // O(1) 
      result.append((a,b,c)) 
     } 
    } 
}           // O(|D|)*O(|D|)=O(|D|^2)