Wie viele Schritte dauert es von n bis 1, indem der größte Teiler abgezogen wird?

50

Inspiriert von dieser Frage bei Mathematics .


Das Problem

Sei neine natürliche Zahl ≥ 2. Nehmen Sie den größten Teiler von n- der sich von nselbst unterscheidet - und subtrahieren Sie ihn von n. Wiederholen, bis Sie bekommen 1.

Die Frage

Wie viele Schritte tut , es zu erreichen nehmen 1für eine bestimmte Anzahl n ≥ 2.

Ausführliches Beispiel

Lassen n = 30.

Der größte Teiler von:

1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

Es dauert 6 Schritte zu erreichen 1.

Eingang

  • Eingabe ist eine ganze Zahl n, wobei n ≥ 2.
  • Ihr Programm sollte die Eingabe bis zum maximalen Ganzzahlwert der Sprache unterstützen.

Ausgabe

  • Geben Sie einfach die Anzahl der Schritte wie 6.
  • Führende / nachfolgende Leerzeichen oder Zeilenumbrüche sind in Ordnung.

Beispiele

f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

Bedarf

  • Sie können Eingaben von STDINBefehlszeilenargumenten als Funktionsparameter oder von der nächstgelegenen Entsprechung erhalten.
  • Sie können ein Programm oder eine Funktion schreiben. Wenn es sich um eine anonyme Funktion handelt, geben Sie bitte ein Beispiel für den Aufruf an.
  • Dies ist also gewinnt die kürzeste Antwort in Bytes.
  • Standardlücken sind nicht zulässig.

Diese Serie gibt es auch bei OEIS: A064097

Ein durch a(1) = 0und a(p) = 1 + a(p-1)if induktiv definierter Quasi-Logarithmus pist prim und a(n*m) = a(n) + a(m)if m,n > 1.

insertusernamehere
quelle
die Eingabeanforderung in Sprachen mit nativen Ganzzahlen mit willkürlicher Genauigkeit zu klären?
Sparr
@Sparr Ich würde sagen, du solltest zumindest bis zu unterstützen 2^32 - 1. Der Rest liegt bei Ihnen und Ihrem System. Hoffe, das hast du mit deiner Frage gemeint.
insertusernamehere
3
Mir gefällt, wie der Titel alles zusammenfasst
Luis Mendo

Antworten:

20

Gelee , 9 Bytes

ÆṪÐĿÆFL€S

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Hintergrund

Die Definition der Sequenz A064097 impliziert dies

Definition

Nach der Produktformel von Euler

Eulers Produktformel

wobei φ die Euler'sche Totientenfunktion bezeichnet und p nur über Primzahlen variiert.

Wir kombinieren beides und leiten daraus das Grundstück ab

erste Eigenschaft

wobei ω die Anzahl der verschiedenen Primfaktoren von n bezeichnet .

Wendet man die resultierende Formel k + 1 mal an, wobei k groß genug ist, dass φ k + 1 (n) = 1 ist , so erhält man

zweite Eigenschaft

Aus dieser Eigenschaft erhalten wir die Formel

Formel

wo die letzte Gleichheit gilt, weil ω (1) = 0 .

Wie es funktioniert

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.
Dennis
quelle
Das ist ein super cleverer Ansatz!
13.
15

05AB1E , 13 11 Bytes

Code:

[DÒ¦P-¼D#]¾

Erläuterung:

[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Verwendet CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
13
Entfernen Sie den ersten Primfaktor (den kleinsten), um das größte Produkt zu erhalten. Wie clever! :-)
Luis Mendo
Ich verstehe, Sie sind der Sprachentwickler
Sarge Borsch
@ SargeBorsch Ja, das ist richtig :)
Adnan
[¼Ñü-¤ÄD#]¾- Ich war kurz davor, ein Byte paarweise zu rasieren, na ja ...
Magic Octopus Urn
-1 Byte: [Ð#Ò¦P-¼]¾. Ðist besser als DD.
Grimmy
11

Pyth, 11 Bytes

fq1=-Q/QhPQ

Testsuite

Eine einfache Wiederholungsschleife.

Erläuterung:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.
isaacg
quelle
das ist ein sehr schöner trick mit filter.
Maltysen
3
Ich verstehe nicht, warum dies die Häufigkeit ausgibt, mit der die Funktion ausgeführt wurde. Ist dies ein undokumentiertes Merkmal von f?
corsiKa
@corsiKa fohne zweites Argument durchläuft alle positiven Ganzzahlen ab 1und gibt den ersten Wert zurück, der für die innere Anweisung true ergibt. Dieser Wert wird in diesem Programm nicht verwendet und gibt die Anzahl der ausgeführten Vorgänge zurück. Nicht undokumentiert, nur unorthodox :) Wenn es hilft, können Sie sich das wie eine forSchleife for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}
vorstellen
@corsiKa Es ist in der Zeichenreferenz auf der rechten Seite des Online-Dolmetschers dokumentiert. Mit nur einem Argument ( f <l:T> <none>) fist die erste Eingabe, bei der A(_)die Wahrheit überwunden ist[1, 2, 3, 4...] .
Dennis
Ah, ich verstehe es jetzt. Diese Eingabe wird verwendet, die Eingabe wird jedoch nie in der Berechnung verwendet . Das erklärt @Maltysen Kommentar von "das ist ein wirklich netter Trick", weil Sie sich nur um die Iterationszahl kümmern, die nicht irgendwo in Ihrem Filter verwendet wird. Ich liebe diese ah-ha Momente !
:)
7

Python 2, 50 49 Bytes

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

Dies wird den letzten Testfall nicht in Kürze beenden ...

Alternativ ist hier ein 48-Byte, das Trueanstelle von 1for zurückgibt n=2:

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)
Sp3000
quelle
6

Gelee , 10 Bytes

ÆfḊPạµÐĿi2

Probieren Sie es online! oder überprüfen Sie die meisten Testfälle . Die letzten Testfälle enden schnell vor Ort.

Wie es funktioniert

ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.
Dennis
quelle
5

Retina , 12

  • 14 Bytes gespart dank @ MartinBüttner
(1 +) (? = \ 1 + $)

Dies setzt voraus, dass die Eingabe unär und die Ausgabe dezimal erfolgt. Wenn dies nicht akzeptabel ist, können wir dies für weitere 6 Bytes tun:

Retina , 18

  • 8 Bytes gespart dank @ MartinBüttner
. +
$ *
(1 +) (? = \ 1 + $)

Online testen - Erste Zeile hinzugefügt, um alle Testfälle auf einmal auszuführen.

Leider wird für die Berechnungen eine Einzahl verwendet, sodass die Eingabe von 2016 155 nicht praktikabel ist.

  • Die erste Stufe (2 Zeilen) konvertiert einfach die Dezimaleingabe in eine unäre Zeichenfolge von 1s
  • Die zweite Stufe (1 Zeile) berechnet den größten Faktor von n unter Verwendung von Regex-Übereinstimmungsgruppen und sieht danach aus und subtrahiert ihn effektiv von n. Dieser reguläre Ausdruck passt so oft wie nötig, um die Anzahl so weit wie möglich zu verringern. Die Anzahl der Regex-Übereinstimmungen entspricht der Anzahl der Schritte und wird von dieser Stufe ausgegeben.
Digitales Trauma
quelle
Ich glaube nicht, dass du das brauchst \b.
Martin Ender
Sie können jedoch viel mehr davon sparen und technisch brauchen Sie auch nicht die erste Stufe .
Martin Ender
@ MartinBüttner Fantastisch! Sehr elegant - danke!
Digitales Trauma
5

Pyth - 15 14 13 Bytes

Ein spezielles Gehäuse 1bringt mich um.

tl.u-N/Nh+PN2

Probieren Sie es hier online aus .

tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1
Maltysen
quelle
1
Eine Sache, die ich immer vergesse ... rohe Gewalt ist oft der golferischste Ansatz
Leaky Nun
Was meinst du mit Spezialgehäuse 1?
Adnan
1
@Adnan der prime Faktorisierung von 1IS [], der einen Fehler verursacht , wenn das erste Element I nehmen. Ich muss es in besonderen Fällen 1tun , damit es wieder zurückkehrt, damit der .uFixpunkt endet. Ich habe einen besseren Weg gefunden als .xtry - außer das hat mir diese 2 Bytes erspart.
Maltysen
Es müssen nur Zahlen> = 2 (> 1) akzeptiert werden.
Solomon Ucko
@SolomonUcko du missverstehst, der .uFestpunkt greift irgendwann 1nach allen Eingaben, an welcher Stelle es spezielle Gehäuse geben muss.
Maltysen
5

JavaScript (ES6), * 44 38

Bearbeiten Sie 6 Bytes gespeichert dank @ l4m2

(* 4 gestrichen ist noch 4)

Rekursive Funktion

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

Weniger golfen

f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

Prüfung

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
<pre id=O></pre>

edc65
quelle
Schön, aber ich denke, Sie sollten die zwei Bytes ausgeben, die benötigt werden, um f (1) == 0 zu machen.
Neil,
@Neil denkt nochmal nach: nein. "Sei n eine natürliche Zahl ≥ 2 ..."
edc65
Ich brauche eine neue Brille.
Neil
Warum nicht f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0?
14 m²,
@ l4m2 richtig, warum nicht? Vielen Dank
edc65
4

Mathematica, 36 Bytes

f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

Eine unbenannte Funktion benötigt dieselben Bytes:

If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

Dies ist eine sehr einfache Implementierung der Definition als rekursive Funktion.

Martin Ender
quelle
4

Oktave, 59 58 55 Bytes

function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Dank Stewie Griffin aktualisiert und 1 Byte gespart

Weitere Aktualisierung, um drei weitere Bytes zu sparen, indem das Ergebnis der Faktorisierung bei der Überprüfung verwendet wird.

Probeläufe:

octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9
dcsohl
quelle
ist das letzte endin der oktave nötig?
9.
Es ist. Mir ist aufgefallen, dass es in Ihren Antworten nicht in matlab enthalten ist, aber Octave erwartet es (wie ich aus Ihren Versuchen in Octave gelernt habe).
dcsohl
4

Haskell, 59 Bytes

f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

Verwendungszweck:

Prelude> f 30
Prelude> 6

Bei großen Zahlen kann dies ein wenig ineffizient sein, da die Liste erstellt wird.

Alexandru Dinu
quelle
1
Listenverständnis und spart <1stattdessen ==0ein paar Bytes: f 1=0;f n=1+f(n-last[a|a<-[1..ndiv2],mod n a<1])
Angs
4

Julia, 56 50 45 39 Bytes

f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

Dies ist eine rekursive Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt.

Ungolfed:

function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

Probieren Sie es online! (beinhaltet alle Testfälle)

6 Bytes gespart dank Martin Büttner und 11 dank Dennis!

Alex A.
quelle
3

PowerShell v2 +, 81 Byte

param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

Brutalste Gewalt.

Übernimmt die Eingabe $a, tritt in eine forSchleife ein, bis $akleiner oder gleich ist 1. In jeder Schleife durchlaufen wir eine andere forSchleife, von der abwärts gezählt wird, $abis wir einen Divisor ( !($a%$i) finden. Im schlimmsten Fall werden wir $i=1als Teiler finden. Wenn wir dies tun, erhöhen Sie unseren Zähler $j, subtrahieren unseren Divisor $a-=$iund $i=0brechen aus der inneren Schleife aus. Irgendwann werden wir einen Zustand erreichen, in dem die äußere Schleife falsch ist (dh erreicht $ahat 1), also ausgeben $jund beenden.

Achtung : Dies wird eine dauern lange Zeit auf eine größere Anzahl, insbesondere Primzahlen. Die Eingabe von 100.000.000 dauert auf meinem Core i5-Laptop ~ 35 Sekunden. Bearbeiten - gerade mit [int]::MaxValue(2 ^ 32-1) getestet , und es dauerte ~ 27 Minuten. Nicht zu schlecht, nehme ich an .

AdmBorkBork
quelle
3

Matlab, 58 Bytes

function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end
Abr001am
quelle
3

Japt , 12 Bytes (nicht konkurrierend)

@!(UµUk Å×}a

Online testen! Nicht konkurrierend, da es eine Reihe von Funktionen verwendet, die nach dem Posten der Herausforderung hinzugefügt wurden.

Wie es funktioniert

@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

Diese Technik wurde von der 05AB1E-Antwort inspiriert . Eine frühere Version verwendet ²¤(Push a 2, Slice off der ersten beiden Elemente) anstelle von, Åweil es ein Byte kürzer ist als s1 (Note Trailing Space); Ich erkannte erst nach der Tatsache, dass, da dies eine 2 an das Ende des Arrays und die Slices von Anfang an anfügt , es in der Tat auf einer ungeraden zusammengesetzten Zahl fehlschlägt, obwohl es auf allen gegebenen Testfällen funktioniert.

ETHproductions
quelle
2

Python 3, 75, 70 , 67 Bytes.

g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

Dies ist eine ziemlich einfache rekursive Lösung. Bei den vielen Testfällen dauert es SEHR lange.

Morgan Thrapp
quelle
2

> <> 32 Bytes

<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

Erwartet die eingegebene Nummer nauf dem Stapel.

Dieses Programm erstellt die vollständige Sequenz auf dem Stapel. Die einzige Zahl, zu der es führen kann, 1ist 2, dass die Erstellung der Sequenz beendet wird, wenn sie 2erreicht ist. Dies bewirkt auch, dass die Größe des Stapels der Anzahl der Schritte entspricht und nicht der Anzahl der Schritte +1.

Sok
quelle
2

Ruby, 43 Bytes

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

Finden Sie die kleinste Zahl i, die sich xteilt, x-iund wiederholen Sie den Vorgang, bis wir sie erreichen 1.

Histokrat
quelle
2

Haskell, 67 Bytes

Hier ist der Code:

a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

Und hier ist ein Grund, warum Haskell großartig ist:

f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

Ja, in Haskell können Sie festlegen -->, dass es äquivalent zu ist ==.

Michael Klein
quelle
2

Matlab, 107 Bytes

a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))
  • Nicht konkurrierend, dies ist nicht die iterative Übersetzung meines letzten Beitrags, sondern nur eine weitere direkte algerbraische Methode. Sie fasst alle Binärlogs aller Primfaktoren zusammen und ist irgendwie mehrdeutig zu veranschaulichen.
  • Ich werde mehr Golf spielen, wenn ich Zeit habe.
Abr001am
quelle
2

MATL, 17 16 Bytes

`tttYfl)/-tq]vnq

Probieren Sie es online

Erläuterung

        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result
Suever
quelle
2

C99, 62 61 Bytes

1 Byte von @Alchymist abgegolft.

f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}  

Rufen Sie als f (x, & y) auf, wobei x die Eingabe und y die Ausgabe ist.

mIllIbyte
quelle
Wenn Sie a% - b testen, können Sie das b-- am Ende vermeiden. Ein ganzes Byte sparen.
Alchymist
2

Clojure, 116 104 Bytes

(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 Bytes, indem ein Bereich gefiltert wird, um ein Vielfaches zu finden, und dann lasteins verwendet wird, um das größte zu erhalten

Naive Lösung, die das vom OP beschriebene Problem im Grunde nur löst. Leider nimmt das Finden des größten Divisors allein etwa die Hälfte der verwendeten Bytes in Anspruch. Zumindest sollte ich von hier aus viel Platz zum Golfen haben.

Vorgolfed und Test:

(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6
Karzigenat
quelle
1
@insertusernamehere Nein, leider, denn das sind alles gültige Bezeichner. Ich habe alle möglichen Leerzeichen entfernt. Wenn ich weiter Golf spielen möchte, muss ich den Algorithmus überarbeiten.
Carcigenicate
2

Perl 6 , 35 Bytes

{+({$_ -first $_%%*,[R,] ^$_}...1)}

Probieren Sie es online!

Wie es funktioniert

{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.
smls
quelle
1

Pyth, 17 16 Bytes

L?tbhy-b*F+1tPb0

Probieren Sie es online! (Das y.vam Ende ist für den Funktionsaufruf)


Ursprüngliche 17 Bytes:

L?tb+1y-b*F+1tPb0

Probieren Sie es online! (Das y.vam Ende ist für den Funktionsaufruf)

(Diese Frage habe ich tatsächlich mit diesem Pyth-Programm beantwortet.)

Undichte Nonne
quelle
Ich habe mich nicht wirklich darum gekümmert, Ihr Programm durchzugehen, aber wenn Sie die rekursive Definition im OP verwenden, uist sie wahrscheinlich kürzer als die tatsächliche Rekursion.
Maltysen
1

Pyke, 11 Bytes (nicht konkurrierend)

D3Phf-oRr;o

Dies verwendet ein neues Verhalten, bei dem, wenn nach einem Sprung eine Ausnahme ausgelöst wird, der Zustand vor dem Sprung wiederhergestellt wird (mit Ausnahme von Variablendefinitionen) und fortgesetzt wird. In diesem Fall entspricht es dem folgenden Python-Code:

# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

Dies ist alles mit Pyke ohne eine while-Schleife möglich - na los!

Probieren Sie es hier aus!

Blau
quelle
1

JavaScript (ES6), 70 54 Bytes

f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

Implementierung der bereitgestellten rekursiven Formel, die jetzt aktualisiert wurde, um mithilfe der Rekursion auch den Divisor zu finden.

Neil
quelle
1

Perl, 57 + 1 ( -pFlag) = 58 Bytes

$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Verwendungszweck:

> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Ungolfed:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}
Denis Ibaev
quelle
1

Clojure, 98 96 Bytes

#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

Verwendet for :when, um den größten Divisor zu finden, Schleifen, bis kein größerer Wert als eins gefunden wird.

NikoNyrh
quelle