Étant donné un entier positif vous pouvez toujours trouver un tuple d'entiers tels que k_1 \ cdot k_2 \ cdot ... \ cdot k_m = n et k_1 | k_2 \ text {,} k_2 | k_3 \ text {,} \ ldots \ text {,} k_ {m-1} | k_m. Ici, a | b signifie que b est un multiple de a , disons "a divise b". Si n> 1, toutes les entrées k_i doivent être au moins égales à 2 . Pour n = 1, nous n'avons pas un tel facteur et nous obtenons donc un tuple vide.$n$$(k_1,k_2,...,k_m)$$k_i \geqslant 2$$k_1 \cdot k_2 \cdot ... \cdot k_m = n$

Si vous êtes curieux de savoir d'où cela vient: cette décomposition est connue sous le nom de décomposition de facteurs invariants dans la théorie des nombres et elle est utilisée dans la classification des groupes abéliens générés de manière finie.

Défi

Étant donné sortie tous ces tuples pour la donnée exactement une fois, dans l' ordre que vous aimez. Les formats de sortie de séquence standard sont autorisés.$n$$(k_1,k_2,...,k_m)$$n$

Exemples

  1: () (empty tuple)
  2: (2)
  3: (3)
  4: (2,2), (4)
  5: (5)
  6: (6)
  7: (7)
  8: (2,2,2), (2,4), (8)
  9: (3,3), (9)
 10: (10)
 11: (11)
 12: (2,6), (12)
108: (2,54), (3,3,12), (3,6,6), (3,36), (6,18), (108)

Connexes: http://oeis.org/A000688 , Liste de toutes les partitions multiplicatives de n

Haskell, 66 62 60 octets

f n=[n|n>1]:[k:l:m|k<-[2..n],l:m<-f$div n k,mod(gcd n l)k<1]

Essayez-le en ligne!

05AB1E , 13 octets

Òœ€.œP€`êʒüÖP

Essayez-le en ligne!

Ò                      # prime factorization of the input
 œ€.œ                  # all partitions
     P                 # product of each sublist
      €`               # flatten
        ê              # sorted uniquified
         ʒ             # filter by:
          üÖ           #  pairwise divisible-by (yields list of 0s or 1s)
            P          #  product (will be 1 iff the list is all 1s)

Gelée , 17 octets

ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ

Essayez-le en ligne!

JavaScript (V8) ,  73  70 octets

$(k_m,k_{m-1},...,k_1)$

f=(n,d=2,a=[])=>n>1?d>n||f(n,d+1,a,d%a[0]||f(n/d,d,[d,...a])):print(a)

Essayez-le en ligne!

Commenté

f = (             // f is a recursive function taking:
  n,              //   n   = input
  d = 2,          //   d   = current divisor
  a = []          //   a[] = list of divisors
) =>              //
  n > 1 ?         // if n is greater than 1:
    d > n ||      //   unless d is greater than n,
    f(            //   do a recursive call with:
      n,          //     -> n unchanged
      d + 1,      //     -> d + 1
      a,          //     -> a[] unchanged
      d % a[0] || //     unless the previous divisor does not divide the current one,
      f(          //     do another recursive call with:
        n / d,    //       -> n / d
        d,        //       -> d unchanged
        [d, ...a] //       -> d preprended to a[]
      )           //     end of inner recursive call
    )             //   end of outer recursive call
  :               // else:
    print(a)      //   this is a valid list of divisors: print it

05AB1E , 17 15 14 octets

ѦIиæʒPQ}êʒüÖP

Très lent pour les cas de test plus volumineux.

-1 octet grâce à @Grimy .

Essayez-le en ligne.

Explication:

Ñ               # Get all divisors of the (implicit) input-integer
 ¦              # Remove the first value (the 1)
  Iи            # Repeat this list (flattened) the input amount of times
                #  i.e. with input 4 we now have [2,4,2,4,2,4,2,4]
    æ           # Take the powerset of this list
     ʒ  }       # Filter it by:
      PQ        #  Where the product is equal to the (implicit) input
         ê      # Then sort and uniquify the filtered lists
          ʒ     # And filter it further by:
           ü    #  Loop over each overlapping pair of values
            Ö   #   And check if the first value is divisible by the second value
             P  #  Check if this is truthy for all pairs

                # (after which the result is output implicitly)

JavaScript, 115 octets

f=(n,a=[],i=1)=>{for(;i++<n;)n%i||(a=a.concat(f(n/i).filter(e=>!(e[0]%i)).map(e=>[i].concat(e))));return n>1?a:[a]}

J'écrirai une explication plus tard

Wolfram Language (Mathematica) , 78 76 72 71 67 octets

If[#>(p=1##2),Join@@If[i∣##,##~#0~i,{}]~Table~{i,2,#/p},{{##2}}]&

Essayez-le en ligne!

Arborescence de recherche récursive.

Solution de force brute, 64 octets :

Union@Cases[Range@#~Tuples~#,{a__,__}/;1a==#&&a>=2&&1∣a:>{a}]&

Modification triviale de ma solution Mathematica pour lister toutes les partitions multiplicatives de n .

$n^n$

Japt , 22 octets

â Åï c à f@¥XשXäv eÃâ

Essayez-le

â Åï c à f@¥XשXäv eÃâ     :Implicit input of integer U
â                          :Divisors
  Å                        :Slice off the first element, removing the 1
   ï                       :Cartesian product
     c                     :Flatten
       à                   :Combinations
         f                 :Filter by
          @                :Passing each sub-array X through the following function
           ¥               :  Test U for equality with
            X×             :  X reduced by multiplication
              ©            :  Logical AND with
               Xä          :  Consecutive pairs of X
                 v         :  Reduced by divisibility
                   e       :  All truthy?
                    Ã      :End filter
                     â     :Deduplicate