Un nombre hautement composite est un entier positif qui a plus de diviseurs que n'importe quel entier positif plus petit. Il s'agit de la séquence OEIS A002182 . Ses 20 premiers mandats sont

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560

Par exemple, 4est dans la séquence car il a 3 diviseurs (à savoir 1, 2, 4), tandis que 3 n'a que 2 diviseurs, 2 a également 2 diviseurs et 1 a 1 diviseurs.

Défi

Étant donné une entrée entière positive n , sortez le n- ème nombre hautement composite ou les n premiers nombres hautement composites, à votre choix (mais le choix doit être le même pour chaque entrée n ).

Règles

Le programme ou la fonction devrait théoriquement fonctionner pour des entrées arbitrairement grandes étant donné un temps et une mémoire infinis, et sans tenir compte des limitations du type de données. Essentiellement, cela signifie qu'il n'est pas nécessaire de coder en dur un nombre fini de valeurs.

En pratique, le programme ou la fonction doit s'exécuter dans un laps de temps raisonnable, disons moins de 1 minute, pour n jusqu'à 20. L'entrée ou la sortie maximale peut être limitée par le type de données standard de votre langue (mais encore une fois, l'algorithme devrait théoriquement fonctionner pour des nombres arbitrairement grands).

Tout format d'entrée et de sortie raisonnable est autorisé, y compris unaire.

Code golf. Le moins d'octets gagne.

05AB1E , 15 14 octets

L'entrée est indexée zéro. Cela signifie que n = 0donne 1, n = 1donne 2, etc. Code:

$µ>DÑgD®›i©¼}\

Explication:

$               # Pushes 1 and input
 µ              # Counting loop, executes until the counting variable is equal to input
  >             # Increment (n + 1)
   DÑ           # Duplicate and calculate all divisors
     gD         # Get the length of the array and duplicate
       ®        # Retrieve element, standardized to zero
        ›i  }   # If greater than, do...
          ©     #   Copy value into the register
           ¼    #   Increment on the counting variable
             \  # Pop the last element in the stack

Calcule n = 19 , ce qui devrait donner 7560environ 10 secondes.

Essayez-le en ligne!

Utilise l' encodage CP-1252 .

Gelée, 15 octets

,®ÆDL€ṛ©0>/?µƓ#

Pour l'entrée n , cela imprime les n premiers nombres hautement composites.

Pour n = 20 , cela prend moins de deux secondes sur Essayez-le en ligne!

Comment ça marche

,®ÆDL€ṛ©0>/?µƓ#  Main link. No implicit input.

            µ    Push the chain to the left on the local link stack.
             Ɠ   Read an integer n from STDIN.
              #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
                 value n times. Return the list of matches.

,®               Pair k with the value in the register (initially 0).
  ÆD             Compute the divisors of k and the register value.
    L€           Count both lists of divisors.
           ?     If
         >/        k has more divisors than the register value:
      ṛ©             Save k in the register and return k.
        0          Else: Return 0.

Version alternative, 13 octets (non concurrente)

Alors que le code ci-dessous fonctionnait dans la dernière version de Jelly qui précède ce défi, la mise en œuvre de Métait très lente et ne respectait pas le délai. Cela a été corrigé.

ÆDL®;©MḢ’>µƓ#

Essayez-le en ligne!

Comment ça marche

ÆDL®;©MḢ’>µƓ#  Main link. No implicit input.

          µ    Push the chain to the left on the local link stack.
           Ɠ   Read an integer n from STDIN.
            #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
               value n times. Return the list of matches.

ÆD             Compute the divisors of k.
  L            Count them.
   ®;          Append the count to the list in the register (initially 0 / [0]).
     ©         Save the updated list in the register.
      M        Obtain all indices the correspond to maximal elements.
       Ḣ       Retrieve the first result.
        ’>     Subtract 1 and compare with k.
               This essentially checks if the first maximal index is k + 2, where
               the "plus 2" accounts for two leading zeroes (initial value of the
               register and result for k = 0).

MATL , 26 24 octets

~XKx`K@@:\~s<?@5MXKx]NG<

Essayez-le en ligne!

Le plus grand nombre actuel de diviseurs trouvés est conservé dans le presse-papiers K. Les nombres hautement composites (HCN) sont conservés directement sur la pile. Une boucle continue de tester les candidats à HCN. Une fois trouvé, il reste sur la pile et le presse-papiers K est mis à jour. La boucle se termine lorsque le nombre souhaité de HCN a été trouvé.

~         % take input implicitly (gets stored in clipboard G). Transform into a 0 
          % by means of logical negation
XKx       % copy that 0 into clipboard K, and delete
`         % do...while
  K       %   push largest number of divisors found up to now
  @       %   push iteration index, i: current candidate to HCN
  @:      %   range [1,...,i]
  \       %   modulo operation
  ~s      %   number of zeros. This is the number of divisors of current candidate
  <       %   is it larger than previous largest number of divisors?
  ?       %   if so: a new HCN has been found
    @     %     push that number
    5M    %     push the number of divisors that was found
    XKx   %     update clipboard K, and delete
  ]       %   end if
  N       %   number of elements in stack
  G<      %   is it less than input? This the loop condition: exit when false
          % end do...while implicitly
          % display all numbers implicitly

Perl, 60 57 + 1 = 58 octets

$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,

Requiert -net gratuit -M5.010| -E:

$ perl -nE'$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,' <<< 10 
120

Comment ça marche:

$,++;
     $==grep$,%$_<1,1..$,;                                # Calculate total numbers of divisors for `$,`
                          $_--,$m=$=if$=>$m;              # Set `$m`ax divisors to `$=`ivisors if `$m>$=`
                                            $_?redo:say$, # Repeat or print

JavaScript (ES6) 72

Mise en œuvre simple. Temps proche de 20 s pour l'entrée 20

x=>{for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;return n}

L'astuce eval pourrait économiser un octet doublant le temps d'exécution

x=>eval("for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;n")

Moins golfé

x=>{
  for(i = e = 0, n = 1; i < x; n++)
  {
    for(d = 1, j = n; --j; )
    {
      if (n%j == 0) 
        ++d;
    }
    if (d > e)
      ++i,
      e = d;
  }
  return n;
}

Pyth, 17 16 octets

1 octet grâce à Jakube

uf<Fml{yPd,GTGQ1

Suite de tests

Prend un n indexé 0 et retourne le nième nombre hautement composite.

Explication:

uf<Fml{yPd,GThGQ1
                     Input: Q = eval(input())
u              Q1    Apply the following function Q times, starting with 1.
                     Then output the result. lambda G.
 f           hG      Count up from G+1 until the following is truthy, lambda T.
          ,GT        Start with [G, T] (current highly comp., next number).
    m                Map over those two, lambda d.
        Pd           Take the prime factorization of d, with multiplicity.
       y             Take all subsets of those primes.
      {              Deduplicate. At this point, we have a list of lists of primes.
                     Each list is the prime factorization of a different factor.
     l               Take the length, the number of factors.
  <F                 Check whether the number of factors of the previous highly
                     composite number is smaller than that of the current number.

Rubis, 70 69 67 66 64 62

->n{r=k=0
0until(r<t=(1..k+=1).count{|d|k%d<1})&&1>n-=t/r=t
k}

Mise en œuvre simple.

C, 98 octets

f,i,n,j;main(m){for(scanf("%d",&n);n--;printf("%d ",i))for(m=f;f<=m;)for(j=++i,f=0;j;)i%j--||f++;}

Essayez-le ici .

Non golfé

f,i,n,j;

main(m)
{
    for(scanf("%d",&n); /* Get input */
            n--; /* Loop while still HCN's to calculate... */
            printf("%d ",i)) /* Print out the last calculated HCN */
        for(m=f;f<=m;) /* Loop until an HCN is found... */
            for(j=++i,f=0;j;) /* Count the number of factors */
                i%j--||f++;
}

Python 3, 97 octets

i=p=q=0;n=int(input())
while q<n:
 c=j=0;i+=1
 while j<i:j+=1;c+=i%j==0
 if c>p:p=c;q+=1
print(i)

Un programme complet qui prend l'entrée de STDIN et imprime la sortie sur STDOUT. Cela renvoie le nth nombre hautement composite indexé sur 1.

Comment ça marche

Il s'agit d'une implémentation simple. L'entrée nest l'indice numérique hautement composite.

Le programme parcourt les entiers i. Pour chaque entier jinférieur à i, i mod jest pris; si c'est le cas 0, jdoit être un facteur de iet le compteur cest incrémenté, donnant le nombre de diviseurs d' iafter looping. pest le nombre de diviseurs le plus élevé précédent, donc si c > p, un nouveau nombre hautement composite a été trouvé et que le compteur qest incrémenté. Une fois q = n, idoit être le nnuméro hautement composite, et celui-ci est imprimé.

Essayez-le sur Ideone

(Cela prend ~ 15 secondes pour n = 20, ce qui dépasse la limite de temps pour Ideone. Par conséquent, l'exemple donné est pour n = 18.)

Python 2, 207 octets

n,i,r,o=input(),1,[],[]
while len(o)<n:
 r+=[(lambda n:len(set(reduce(list.__add__,([i,n//i]for i in range(1,int(n**0.5)+1)if n%i==0)))))(i)];h=max(r)
 if r.index(h)>i-2 and r.count(h)<2:o+=[i]
 i+=1
print o

Utilise la même méthode que la réponse Jelly de Dennis. Calcule les 20 premiers termes en <2secondes.