Algorithme pour trouver le plus petit nombre avec un nombre donné de facteurs

Ce qui est le plus efficace algorithme on peut penser que, étant donné un nombre naturel nretourne le moins de nombre naturel x avec n diviseurs positifs (y compris 1 et x)? Par exemple, étant donné 4 l'algorithme devrait entraîner 6 (diviseurs: 1,2,3,6); c'est à dire 6 est le plus petit nombre ayant 4 facteurs distincts. De même, étant donné 6, l'algorithme devrait aboutir à 12 (diviseurs: 1,2,3,4,6,12); c'est à dire 12 est le plus petit nombre ayant 6 facteurs distincts

En termes de performance dans le monde réel, je suis à la recherche d'un algorithme évolutif qui peut donner des réponses de l'ordre de 1020 dans les 2 secondes sur une machine qui est capable de faire 107 de calculs par seconde.

source d'informationauteur user401445 | 2012-01-14

  1. 12

    http://www.primepuzzles.net/problems/prob_019.htm

    b) Jud McCranie, T. W. A. Baumann & Enoch Haga envoyé fondamentalement la même
    procédure pour trouver N(d) pour un d:

    1. Factoriser d comme un produit de ses diviseurs premiers: d = p11 * p22 *p33 *...
    2. convertir cette factorisation dans un autre arithmétiquement, l'équivalent de la factorisation, composé de non-alimenté de façon monotone décroissante et non
      necesarilly facteurs premiers... (uf!...) d = p11 * p22 *p33 *... =
      b1 * b2 * b3...       tels que b1 ≥ b2 ≥ b3...

      Vous devez comprendre que pour chaque d, il y a plusieurs
      arithmétiquement, l'équivalent factorisations qui peut être effectué: par exemple:

      si d = 16 = 24 puis il y a 5 équivalent factorisations:
      d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16
    3. N est le nombre minimal résultant de l'informatique 2b1-1 * 3b2-1 * 5b3-1 * ... pour tous l'équivalent factorisations de d. Sur le même exemple:

      N(16) = le minimum de ces {2 * 3 * 5 * 7, 23 * 3 * 5, 23 * 3327 * 3, 215} = 23 * 3 * 5 = 120

    Mise à jour: Avec des chiffres autour de 1020prêtez attention aux notes par Christian Bau cité sur la même page.