Ilość wysoce kompozyt jest dodatnią liczbą całkowitą, która ma więcej niż którykolwiek dzielników mniejsze dodatnie liczby całkowitej. To jest sekwencja OEIS A002182 . Pierwsze 20 warunków to

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

Na przykład 4jest w sekwencji, ponieważ ma 3 dzielniki (a mianowicie 1, 2, 4), podczas gdy 3 ma tylko 2 dzielniki, 2 ma również 2 dzielniki, a 1 ma 1 dzielniki.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą wejściową n , wypisz n-tą wysoce złożoną liczbę lub pierwsze n wysoce złożonych liczb, według własnego wyboru (ale wybór musi być taki sam dla każdego wejścia n ).

Zasady

Program lub funkcja powinna teoretycznie działać dla dowolnie dużych danych wejściowych, biorąc pod uwagę nieskończony czas i pamięć, bez uwzględnienia ograniczeń typów danych. Zasadniczo nie oznacza to zakodowania na stałe skończonej liczby wartości.

W praktyce program lub funkcja powinna działać w rozsądnym czasie, powiedzmy krócej niż 1 minutę, od n do 20. Maksymalne wejście lub wyjście może być ograniczone przez standardowy typ danych języka (ale znowu algorytm powinien teoretycznie działać dla dowolnie dużych liczb).

Dowolny rozsądny format wejściowy i wyjściowy jest dozwolony, w tym jednoargumentowy.

Kod golfa. Wygrywa najmniej bajtów.

05AB1E , 15 14 bajtów

Dane wejściowe są indeksowane od zera. Oznacza to, że n = 0daje 1, n = 1daje 2itp. Kod:

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

Wyjaśnienie:

$               # 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

Oblicza n = 19 , co powinno dać się 7560za około 10 sekund.

Wypróbuj online!

Wykorzystuje kodowanie CP-1252 .

Galaretka, 15 bajtów

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

Dla wejścia n drukowane jest pierwsze n wysoce złożonych liczb.

Dla n = 20 zajmuje mniej niż dwie sekundy. Wypróbuj online!

Jak to działa

,®Æ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.

Wersja alternatywna, 13 bajtów (niekonkurująca)

Podczas gdy poniższy kod działał w najnowszej wersji Jelly, która poprzedza to wyzwanie, wdrożenie Mbyło bardzo wolne i nie było zgodne z terminem. Zostało to naprawione.

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

Wypróbuj online!

Jak to działa

Æ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 bajtów

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

Wypróbuj online!

Aktualnie największa liczba znalezionych dzielników jest przechowywana w schowku K. Wysoko złożone liczby (HCN) są przechowywane bezpośrednio na stosie. Pętla testuje kandydatów do HCN. Po znalezieniu pozostawia się go na stosie, a schowek K jest aktualizowany. Pętla kończy się po znalezieniu żądanej liczby HCN.

~         % 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 bajtów

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

Wymaga -ni za darmo -M5.010| -E:

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

Jak to działa:

$,++;
     $==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

Prosta implementacja. Czas blisko 20 sekund na wejście 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}

Sztuczka eval może zaoszczędzić bajt podwajający czas działania

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

Mniej golfa

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 bajtów

1 bajt dzięki Jakube

uf<Fml{yPd,GTGQ1

Zestaw testowy

Pobiera n indeksowane przez 0 i zwraca n-tą wysoce złożoną liczbę.

Wyjaśnienie:

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.

Ruby, 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}

Prosta implementacja.

C, 98 bajtów

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++;}

Wypróbuj tutaj .

Bez golfa

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 bajtów

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)

Pełny program, który pobiera dane wejściowe ze STDIN i drukuje dane wyjściowe do STDOUT. Zwraca to nwysoce złożoną liczbę th1 zindeksowaną.

Jak to działa

Jest to prosta implementacja. Dane wejściowe nto wysoce złożony indeks liczb.

Program iteruje po liczbach całkowitych i. Dla każdej liczby całkowitej jponiżej i, i mod jsą zastosowane; jeśli tak jest 0, jmusi być współczynnikiem, ia licznik cjest zwiększany, podając liczbę dzielników ipo zapętleniu. pjest poprzednią najwyższą liczbą dzielników, więc jeśli c > pzostanie znaleziona nowa liczba bardzo złożona, a licznik qzostanie zwiększony. Raz q = n, imusi być nth liczba wysoce kompozyt, a ta jest drukowana.

Wypróbuj na Ideone

(Trwa to około 15 sekund n = 20, co przekracza limit czasowy dla Ideone. Stąd podany przykład dotyczy n = 18).

Python 2, 207 bajtów

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

Używa tej samej metody, co odpowiedź Jelly'ego „Jelly”. Oblicza pierwsze 20 wyrazów w <2sekundach.