Ein Teiler einer Zahl n ist eine beliebige Zahl, die n gleichmäßig teilt , einschließlich 1 und n selbst. Die Anzahl der Teiler d (n) gibt an, wie viele Teiler eine Zahl hat. Hier ist d (n) für das erste Paar n:

n    divisors    d(n)
1    1           1
2    1, 2        2
3    1, 3        2
4    1, 2, 4     3
5    1, 5        2
6    1, 2, 3, 6  4

Wir können wiederholt die Anzahl der Teiler von einer Zahl subtrahieren. Beispielsweise:

16                  = 16
16 - d(16) = 16 - 5 = 11
11 - d(11) = 11 - 2 = 9
 9 - d( 9) =  9 - 3 = 6
 6 - d( 6) =  6 - 4 = 2
 2 - d( 2) =  2 - 2 = 0

In diesem Fall dauerte es 5 Schritte, um zu 0 zu gelangen.

Schreiben Sie ein Programm oder eine Funktion, die bei einer nichtnegativen Zahl n die Anzahl der Schritte zurückgibt, die erforderlich sind, um sie durch wiederholtes Subtrahieren der Anzahl der Teiler auf 0 zu reduzieren.

Beispiele:

0, 0
1, 1
6, 2
16, 5
100, 19
100000, 7534

Gelee, 10 9 Bytes

1 Byte dank Dennis ♦ .

Port meiner Antwort in Pyth .

ÆDLạµÐĿL’

Probieren Sie es online!

Testsuite.

Erläuterung

_ÆDL$$ÐĿL’
      ÐĿ    Repeat the following until result no longer unique:
 ÆD             Yield the array of the divisors
   L            Yield the length of the array
_               Subtract that from the number
        L   Number of iterations
         ’  Minus one.

Python, 49 Bytes

f=lambda n:n and-~f(sum(n%~x<0for x in range(n)))

orlp hat geholfen, ein Byte zu retten! Und Sp3000 sparte zwei weitere. Vielen Dank!

C, 52 Bytes

g,o;l(f){for(g=o=f;o;f%o--||--g);return f?1+l(g):0;}

Pyth, 10 Bytes

tl.ulf%NTS

Testsuite.

Erläuterung

tl.ulf%NTS
tl.ulf%NTSNQ  implicit variables at the end
           Q  obtain the input number
  .u      N   repeat the following until result no longer unique:
         S        generate range from 1 to N
     f            filter for:
      %NT             T in that range, which N%T is truthy (not zero)
    l             length of that list
                  that means, we found the number of "non-divisors" of N
tl            number of iterations, minus 1.

Julia, 31 Bytes

f(n)=n<1?0:f(sum(n%(1:n).>0))+1

Einfache rekursive Implementierung.

MATL , 14 Bytes

`t~?x@q.]t:\zT

Probieren Sie es online!

Erläuterung

`            T  % Infinite loop
 t~?    ]       % Duplicate number. Is it non-zero?
    x@q.        % If so: delete number, push iteration index minus 1, break loop
         t:\    % Duplicate, range, modulo (remainder). Divisors give a 0 remainder
            z   % Number of non-zero elements; that is, of non-divisors

JavaScript (ES6), 64 51 Byte

f=n=>n&&[...Array(m=n)].map((_,i)=>m-=n%++i<1)|f(m)+1

Fragen Sie mich nicht, warum ich unnötigerweise die Schwanzrekursion verwendet habe.

Java, 147 93

a->{int k,i,n=new Integer(a),l=0;for(;n!=0;n-=k)for(l+=k=i=1;i<n;)if(n%i++==0)++k;return l;}

05AB1E, 12 10 Bytes

Code:

[Ð>#Ñg-¼]¾

Erläuterung:

[           # start infinite loop
 Ð          # triplicate current number
  >#        # increase by 1 and break if true
    Ñg      # get number of divisors
      -     # subtract number of divisors from number
       ¼    # increase counter
        ]   # end loop
         ¾  # print counter

Probieren Sie es online aus

Edit: 2 Bytes gespeichert und ein Fehler mit Eingang 0 dank @Adnan behoben

R, 50 Bytes

Ziemlich einfache Implementierung. Probieren Sie es online aus

z=scan();i=0;while(z>0){z=z-sum(z%%1:z<1);i=i+1};i

Mathcad, [tbd] Bytes

Das Mathcad-Byte-Äquivalenzschema muss noch ermittelt werden. Unter Verwendung einer groben Tastenäquivalenz verwendet das Programm ungefähr 39 "Bytes". Beachten Sie, dass der while- und der Programmieroperator jeweils nur eine Tastatureingabe ausführen (ctl-] bzw. ctl-shft- #). Sie können tatsächlich nur auf diese Weise über die Tastatur eingegeben werden.

Was Sie sehen, ist genau das, was auf einem Mathcad-Arbeitsblatt abgelegt wird. Mathcad wertet die Gleichungen / Programme aus und legt die Ausgabe auf demselben Blatt ab (z. B. nach dem Bewertungsoperator '=' oder auf dem Plot).

MATL, 13 Bytes

tX`t:\ztt]Nq&

Probieren Sie es online aus

Erläuterung:

t               % Duplicate input
 X`      ]      % while loop, consumes 1 input
   t:\z         % calculates n-d(n), by counting number non-divisors
       tt       % dupe twice, for while loop condition, next iteration and to keep in stack
          Nq&   % get stack size, decrement, display that value

Mathematica, 35 Bytes

If[#<1,0,#0[#-0~DivisorSigma~#]+1]&

Gutes altes gebrauchen DivisorSigma. @ MartinBüttner stellt folgende Alternativen fest:

If[#<1,0,#0[#-DivisorSum[#,1&]]+1]&
f@0=0;f@n_:=f[n-DivisorSum[n,1&]]+1

Hoon , 93 76 Bytes

|=
r/@
?~
r
0
+($(r (sub r (lent (skim (gulf 1^r) |=(@ =(0 (mod r +<))))))))

Ungolfed:

|=  r/@
?~  r
  0
=+  (skim (gulf 1^r) |=(@ =(0 (mod r +<))))
+($(r (sub r (lent -))))

Gibt eine Funktion zurück, die ein Atom annimmt. r . Erstellen Sie einen Zwischenwert, der alle Entwickler von r(Liste erstellen [1..n]) enthält. Behalten Sie nur die Elemente bei, für die (mod ri) ​​== 0 ist. Wenn rNull ist, wird Null zurückgegeben, andernfalls wird der inkrementierte Wert der Rekursion mit r = r- (Längenteiler) zurückgegeben.

Der Code wie er ist braucht eine blöde Zeit, um für n = 100.000 ausgewertet zu werden, nur weil das Finden der Entwickler für große Zahlen eine riesige Liste und Karten darüber ergibt. Wenn Sie sich die Teiler merken, erhalten Sie die richtige Ausgabe für n = 10.000, aber ich habe nicht auf 100.000 gewartet

Haskell, 43 40 39 Bytes

g 0=0;g n=1+g(sum$min 1.mod n<$>[1..n])

Einfacher rekursiver Ansatz. Anwendungsbeispiel: g 16-> 5.

Bearbeiten: @Lynn 3 4 Bytes gespeichert . Vielen Dank!

PowerShell v2 +, 74 bis 67 Byte

param($n)for($o=0;$n-gt0){$a=0;1..$n|%{$a+=!($n%$_)};$n-=$a;$o++}$o

Scheint im Vergleich zu anderen Antworten ziemlich langwierig ...

Übernimmt die Eingabe $n, tritt in eine forSchleife mit der Bedingung ein, $ndie größer als ist 0. Bei jeder Schleifeniteration setzen wir Helfer $aund durchlaufen dann jede Zahl von 1bis zu $n. Jede innere Schleife wird mit jeder Zahl verglichen, um festzustellen, ob es sich um einen Divisor handelt. In diesem Fall erhöhen wir unseren Helfer $a(mit Boolescher Negation und implizitem Cast-to-Int). Dann subtrahieren wir, wie viele Teiler wir gefunden haben, $n-=$aund erhöhen unseren Zähler $o++. Schließlich geben wir aus $o.

Die Ausführung dauert lange , da es sich um ein wichtiges for-loop-Konstrukt handelt. Das Ausführen n = 10,000auf meinem Computer (1 Jahr alter Core i5) dauert beispielsweise fast 3 Minuten.

Racket - 126 Bytes Bis zu 98 Bytes 91 Bytes

Eine extrem naive Lösung - könnte wahrscheinlich mit einem anständigen Algorithmus und einigen Lisp-Tricks, die ich nicht kenne, viel reduziert werden

(define(g x[c 0][d 0][i 2])(cond[(= x 0)c][(= i x)(g d(+ 1 c))][(=(modulo x i)0)(g x c d(+ 1 i))][else(g x c(+ 1 d)(+ 1 i))]))

Bearbeiten: Erklärung auf Anfrage. Wie gesagt, dies ist eine extrem naive rekursive Lösung und kann sehr viel kürzer sein.

(define (g x [c 0] [d 0] [i 2]) ;g is the name of the function - arguments are x (input), c (counter for steps), d (non-divisor counter), i (iterator)
  (cond
    [(= x 0) c] ;once x gets to 0 c is outputted
    [(= i x) (g d (+ 1 c))] ;if iterator reaches x then we recurse with d as input and add 1 to c
    [(= (modulo x i) 0) (g x c d (+ 1 i))] ;checks if iterator is non divisor, then adds it to d and increments iterator
    [else(g x c (+ 1 d) (+ 1 i))])) ;otherwise just increments iterator

Edit 2: 98-Byte-Version mit einem weniger dummen Algorithmus (immer noch ziemlich dumm und kann kürzer sein)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(cdr(build-list x values))))))))

Erläuterung:

(define (g x) ;function name g, input x
  (if (< x 1)
      0 ;returns 0 if x < 1 (base case)
      (+ 1 ;simple recursion - adds 1 to output for each time we're looping
         (g (length ;the input we're passing is the length of... 
              (filter (λ (y) (> (modulo x y) 0)) ;the list where all numbers which are 0 modulo x are 0 are filtered out from...
                             (cdr (build-list x values)))))))) ;the list of all integers up to x, not including 0

Bearbeiten 3: Gespeicherte 7 Bytes durch den Austausch (cdr(build-list x values))mit(build-list x add1)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(build-list x add1)))))))

> <> , 52 + 2 = 54 Bytes

Die eingegebene Nummer muss beim Programmstart auf dem Stack vorhanden sein, damit das -vFlag +2 Bytes enthält . Probieren Sie es online!

:0)?v~ln;>~$-]
03[}\::
@@:$<    v?=0:-1}+{~$?@@01%@:

4 lästige Bytes, die bei Ausrichtungsproblemen verschwendet werden. Bah.

Dieser funktioniert durch Erstellen der Sequenz von nbis0 auf dem Stapel erstellt wird. Sobald 0 erreicht ist, platziere es und gib die Länge des verbleibenden Stapels aus.

Übrigens läuft es O(n^2)pünktlich, also würde ich es nicht versuchen n = 100000...

> <> , 36 + 3 = 39 Bytes

:?v~ln; >~&
:}\0&
+&>1-:?!^:{:}$%0)&

Die Implementierung ist mit jeder Iteration relativ einfach sum(n%k>0 for k in range(1,n-1)). +3 Bytes für das -vFlag pro Meta .

Probieren Sie es online!

Ruby, 42 Bytes

f=->n{n<1?0:1+f[n-(1..n).count{|i|n%i<1}]}

Beim größten Testfall ist ein Stapelüberlauffehler aufgetreten. 100000Hier ist also eine iterative Version innerhalb von 49 Bytes . Dauert jedoch angesichts der O(N^2)Komplexität eine Weile .

->n{c=0;c+=1 while 0<n-=(1..n).count{|i|n%i<1};c}

Perl 5, 40 Bytes

sub f{@_?(1,f((1)x grep@_%$_,1..@_)):()}

Eingabe und Ausgabe erfolgen als Listen der erforderlichen Kopienanzahl von 1.

C #, 63 Bytes

int F(int n)=>n<1?0:F(Enumerable.Range(1,n).Count(i=>n%i>0))+1;

Eigentlich 17 Bytes

";╗R`╜%`░l;"£╬klD

Probieren Sie es online! (Hinweis: Der letzte Testfall läuft bei TIO ab.)

Erläuterung:

";╗R`╜%`░l;"£╬klD
"          "£╬     while top of stack is truthy, call the function:
 ;╗                  push a copy of n to reg0
   R                 range(1,n+1) ([1,n])
    `  `░l             push the number of values where the following is truthy:
     ╜%                  k mod n
                       (this computes the number of non-divisors of n)
          ;            make a copy
              klD  push entire stack as list, count number of items, subtract 1
                   (the result is the number of times the function was called)