Finden Sie die glatteste Zahl

59

Ihre Herausforderung besteht darin, die glatteste Zahl in einem bestimmten Bereich zu finden. Mit anderen Worten, finde die Zahl, deren größter Primfaktor der kleinste ist.

Eine glatte Zahl ist eine Zahl, deren größter Primfaktor klein ist. Zahlen dieses Typs sind nützlich für den schnellen Fourier-Transformationsalgorithmus, die Kryptoanalyse und andere Anwendungen.

Über den Bereich 5, 6, 7, 8, 9, 10ist beispielsweise 8 die glatteste Zahl, da der größte Primfaktor von 8 2 ist, während alle anderen Zahlen einen Primfaktor von 3 oder mehr haben.

Eingabe: Die Eingabe besteht aus zwei positiven Ganzzahlen, die einen Bereich definieren. Die minimal zulässige Ganzzahl im Bereich ist 2. Sie können wählen, ob der Bereich inklusive, exklusiv, semi-exklusiv usw. ist, solange ein beliebiger Bereich innerhalb der Grenzen Ihrer Sprache angegeben werden kann. Sie können die Zahlen über die Funktionseingabe, stdin, das Befehlszeilenargument oder eine entsprechende Methode für Ihre Sprache eingeben. Keine Kodierung zusätzlicher Informationen in der Eingabe.

Ausgabe: Gibt eine oder mehrere Ganzzahlen im Eingabebereich zurück, druckt sie aus oder entspricht ihnen, die maximal glatt sind (minimaler größter Faktor). Die Rückgabe mehrerer Ergebnisse ist optional. Wenn Sie sich jedoch dafür entscheiden, müssen die Ergebnisse klar abgegrenzt werden. Das native Ausgabeformat eignet sich für mehrere Ergebnisse.

Bitte geben Sie in Ihrer Antwort an, wie Sie Inputs aufnehmen und Outputs liefern.

Wertung: Code Golf. Zählen Sie nach Zeichen, wenn Sie in ASCII geschrieben sind, oder nach 8 * Bytes / 7, wenn Sie nicht in ASCII geschrieben sind.

Testfälle:

Hinweis: Dies sind Bereiche im Python-Stil, einschließlich des unteren Endes, aber nicht des oberen Endes. Ändern Sie nach Bedarf Ihr Programm. Es ist nur ein Ergebnis erforderlich.

smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002
isaacg
quelle
Sind Bereiche zulässig, die als (Anfang, Länge) anstelle von (Anfang, Ende) angegeben wurden?
CodesInChaos
1
@CodesInChaos Sicher. Es fällt unter die "oder was auch immer" -Klausel.
isaacg
3
Ich sehe keinen Sinn darin, Nicht-ASCII-Antworten zu bestrafen. Es wäre einfacher, in allen Fällen nur Bytes zu zählen.
nyuszika7h
1
@ nyuszika7h Ascii ist bedeutend kleiner als ein Byte - es werden nur 7 Bits verwendet. Deshalb bezeichne ich ein Zeichen mit 7 Bits und skaliere andere Sprachen entsprechend. Wenn die Sprache jedoch kein ASCII-Format ist, aber alle Zeichen in 7 Bit packen kann, werde ich den Zuschlag nicht anwenden. Siehe J / K vs. APL. tl; dr Bytes ist einfacher, gibt aber APL et. al. Ein subtiler, aber unfairer Vorteil.
Isaacg
3
@isaacg Sie fördern die Erstellung von Pseudosprachen mit kleineren Zeichensätzen. Wenn wir 7-Bit-Zeichensätze erhalten, die sich von den 8-Bit-Zeichensätzen unterscheiden, kann jemand die meisten modernen Sprachen in 6 Bits packen (64 Zeichen bringen uns AZ, 0-9, eine Handvoll Leerzeichen, 20 Interpunktionszeichen und ein paar zu ersparen). .
Sparr

Antworten:

99

CJam - 13

q~,>{mfW=}$0=

Versuchen Sie es unter http://cjam.aditsu.net/

Beispiel Eingabe: 2001 2014
Beispiel Ausgabe:2002

Erläuterung:

q~Liest und wertet die Eingabe aus. Durch Drücken der 2 Zahlen auf dem Stapel (z. B. min und max)
,wird ein Array [0 1 ... max-1] erstellt,
>das das Array ab min schneidet, was zu [min ... max-1] führt.
{…}$sortiert das Array mithilfe des Blocks, um den Sortierschlüssel zu berechnen. Ruft
mfein Array mit allen Primfaktoren einer Zahl ab, um
W=das letzte Element des Arrays zu erhalten (W = -1), wodurch der größte Primfaktor erhalten wird, der als ein verwendet werden soll Sortierschlüssel
0=erhält das erste Element des (sortierten) Arrays

aditsu
quelle
38
Nun, ich denke das ist es.
Eric Tressler
5
Ich muss Pyth eine Faktorisierungsfunktion hinzufügen.
Isaacg
6
Diese Sprache ist Zauberei.
Brobin
8
Dies ist so nah dran, nur ein paar HQ9 + s ** t zu ziehen, wie es nur sein kann, ohne ein Schlupfloch zu werden. Genial!
Ingo Bürk
25
ヽ ヽ ͜ ل͜ ຈ ༽ ノmfWjemand hat es in 13 Zeichen gelöst.
Internet besteht aus Catz
66

Regex ( .NET PCRE-Version), 183 129 Bytes

Versuchen Sie das nicht zu Hause!

Dies ist nicht wirklich ein Anwärter auf den Sieg. Aber Eric Tressler schlug vor, dieses Problem nur mit einer Regex zu lösen, und ich konnte nicht widerstehen, es auszuprobieren. Dies könnte möglich ist , in PCRE als auch (und sogar noch kürzer, siehe unten), aber ich wählte .NET , weil meine Lösung mit beliebiger Länge Lookbehinds benötigt. Auf geht's:

(?<=^(1+),.*)(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((11+)(?=.*(?=\7$)(?!(11+?)\8+$))(?=\7+$)|(?!(11+)\9+$)1+)).*(?=\2$)(?=\6)))1+

Die Eingabe wird als ein durch Kommas getrennter Bereich codiert, in dem beide Zahlen in unärer Notation mit 1s angegeben werden. Die Übereinstimmung ist die nachfolgende S1, wobei Sdie glatteste Zahl im Bereich ist. Krawatten werden zugunsten der kleinsten Zahl gebrochen.

Das zweite Beispiel aus der Frage wäre also die folgende Zeichenfolge (Übereinstimmung unterstrichen)

111111111,1111111111111111
                 =========

Es basiert auf der (mittlerweile bekannten) Prime-Checking-Regex , deren Variationen sage und schreibe sechsmal eingebettet sind.

Hier ist eine Version mit freien Abständen und Kommentaren für diejenigen, die wissen wollen, was los ist.

# Note that the beginning of the match we're looking for is somewhere
# in the second part of the input.
(?<=^(1+),.*)          # Pick up the minimum range MIN in group 1
(?=\1)                 # Make sure there are at least MIN 1s ahead

                       # Now there will be N 1s ahead of the cursor
                       # where MIN <= N <= MAX.


(?=(                   # Find the largest prime factor of this number
                       # store it in group 2.
  (11+)                # Capture a potential prime factor P in group 3
  (?=                  # Check that it's prime
    .*(?=\3$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?!(11+?)\4+$)     # Check that the remaining 1s are not composite
  )
  (?=\3+$)             # Now check that P is a divisor of N.
|                      # This does not work for prime N, so we need a 
                       # separate check
  (?!(11+)\5+$)        # Make sure that N is prime.
  1+                   # Match N
))

(?!                    # Now we need to make sure that here is not 
                       # another (smaller) number M with a smaller 
                       # largest prime factor

  .+                   # Backtrack through all remaining positions
  (?=\1)               # Make sure there are still MIN 1s ahead

  (?:
    (?!\2)             # If M is itself less than P we fail 
                       # unconditionally.
  |                    # Else we compare the largest prime factors.
    (?=(               # This is the same as above, but it puts the
                       # prime factor Q in group 6.
      (11+)
      (?=
        .*(?=\7$)
        (?!(11+?)\8+$)
      )
      (?=\7+$)
    |
      (?!(11+)\9+$)
      1+
    ))
    .*(?=\2$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?=\6)             # Try to still match Q (which means that Q is
                       # less than P)
  )
)
1+                     # Grab all digits for the match

Sie können es online testen hier . Versuche es aber nicht mit zu großen Eingaben, ich übernehme keine Garantie für die Leistung dieses Monsters.

Bearbeiten:

Am Ende habe ich dies auf PCRE portiert (was nur zwei Schritte erfordert) und den regulären Ausdruck um fast ein Drittel verkürzt. Hier ist die neue Version:

^(1+),.*?\K(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((?2))).*(?=\2$)(?=\6)))1+

Dies ist im Wesentlichen dasselbe, mit zwei Änderungen:

  • PCRE unterstützt kein Lookbehind mit beliebiger Länge (mit dem ich die Into- MINGruppe erstellt habe 1). PCREUnterstützt jedoch, dass \Kder Beginn der Übereinstimmung auf die aktuelle Cursorposition zurückgesetzt wird. Somit (?<=^(1+),.*)wird ^(1+),.*?\K, was schon zwei Bytes spart.
  • Die wirklichen Einsparungen ergeben sich aus der Rekursionsfunktion von PCRE. Eigentlich verwende ich keine Rekursion, aber Sie können sie verwenden (?n), um die Gruppe nerneut abzugleichen, ähnlich wie bei einem Unterprogrammaufruf. Da der ursprüngliche reguläre Ausdruck den Code zum zweimaligen Ermitteln des größten Primfaktors einer Zahl enthielt, konnte ich den gesamten Hauptteil des zweiten durch einen einfachen ersetzen (?2).
Martin Ender
quelle
37
Heilige Mutter Gottes
Newb
1
@ Timwi Ich muss überprüfen, ob der größte Primfaktor (Gruppe 3oder 7) tatsächlich Primzahl ist. Dies setzt voraus, dass nach der ersten Erfassung eine weitere Kopie des Faktors vorhanden ist, was bei Primzahlen nicht der Fall wäre. Während ich das in .NET umgehe, indem ich irgendwo einen Lookbehind einsetze, so dass ich mich zur Überprüfung etwas zurückziehen könnte, wäre dies in der kürzeren PCRE-Version aufgrund des Fehlens von Lookbehinds mit variabler Länge nicht möglich. Wahrscheinlich ist möglich , dass etwas zu verkürzen, aber ich glaube nicht , nur die Änderung +zu *Werke.
Martin Ender
2
@MartinEnder Hi! Ich stelle mir vor, Sie haben diese Herausforderung längst gemeistert, aber ich bin gerade reingesurft, habe eine reguläre Lösung gefunden und konnte Ihre Warnung am Anfang dieses Beitrags nicht ignorieren :) Ich finde es schwierig, den Code anderer Leute zu spielen. Nachdem ich mir Ihren regulären Ausdruck angesehen hatte und mich verwirrt hatte, versuchte ich es von Grund auf und kam zu folgendem (.*),.*?\K(?=(..+)((?=((?(R)\6|\2))*$).*(?=\4$)(?!(..+)\5+$)))(?!.+(?=\1)(?=(..+)(?3)).*(?!\2)\6).+ Ergebnis : 99 Bytes in PCRE. Außerdem bin ich auf viele Ihrer Arbeiten auf dieser Website gestoßen und bin ein großer Fan: D Ich freue mich auf einen Regex-Kampf in der Zukunft!
Jaytea
1
Ich habe mit diesem Kommentar Codegolf gespielt, daher möchte ich hier nur das Addendum einfügen: Sie können 4b abschneiden, \4$indem Sie den Lookahead herausnehmen und nach dem negativen Lookahead aufkleben, aber dies beeinträchtigt die Leistung erheblich (jede Untergruppe von Ziffern <= \ 4 wird nicht nur auf \ 4 selbst, sondern auch auf Kompositität geprüft und schlägt bei längeren Eingaben fehl.
Jaytea
1
@jaytea Tut mir leid, dass ich mich für immer darum gekümmert habe. Da Sie die Sache von Grund auf neu geschrieben haben, sollten Sie eine separate Antwort veröffentlichen. Das ist eine großartige Punktzahl und Sie verdienen die Anerkennung dafür. :)
Martin Ender
16

Regex (PCRE-Geschmack), 66 (65🐌) Bytes

Inspiriert davon, dass sowohl Martin Ender als auch Jaytea , zwei Regex-Genies, Regex-Lösungen für diesen Code-Golf geschrieben haben, habe ich meine eigenen von Grund auf neu geschrieben. Der berühmte reguläre Ausdruck für die Erstprüfung kommt in meiner Lösung nirgendwo vor.

Lesen Sie dies nicht, wenn Sie nicht möchten, dass unäre Regex-Magie für Sie verwöhnt wird. Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in ECMAScript regex zu lösen:

  1. Primzahlen abgleichen (falls Sie noch nicht mit Regex vertraut sind)
  2. Kombiniere Potenzen von 2 (falls du es noch nicht getan hast). Oder arbeiten Sie sich einfach durch Regex Golf , zu dem Prime und Powers gehören. Stellen Sie sicher, dass Sie sowohl die Classic- als auch die Teukon-Problemmenge ausführen.
  3. Finden Sie den kürzesten Weg, um Potenzen von N abzugleichen, wobei N eine Konstante ist (dh in der Regex angegeben, nicht die Eingabe), die zusammengesetzt sein kann (aber nicht sein muss). Passen Sie zum Beispiel Potenzen von 6 an.

  4. Finden Sie einen Weg, um N-te Potenzen abzugleichen, wobei N eine Konstante> = 2 ist. Passen Sie beispielsweise perfekte Quadrate an. (Zum Aufwärmen Primzahlen angleichen .)

  5. Stimmen Sie mit den richtigen Multiplikationsanweisungen überein. Dreieckige Zahlen abgleichen.

  6. Stimmen Sie mit Fibonacci-Zahlen überein (wenn Sie so verrückt sind wie ich) oder wenn Sie sich an etwas Kürzeres halten möchten, stimmen Sie mit den korrekten Exponentiationsaussagen überein (zum Aufwärmen geben Sie den Logarithmus in Basis 2 mit einer Potenz von 2 als Übereinstimmung zurück). Bonus, machen Sie dasselbe für eine beliebige Zahl, runden Sie sie, wie Sie möchten, oder für Fakultätszahlen (zum Aufwärmen passen Sie die Primorialzahlen an ).

  7. Kombiniere viele Zahlen (wenn du so verrückt bist wie ich)

  8. Berechnen Sie eine irrationale Zahl mit der gewünschten Genauigkeit (z. B. dividieren Sie die Eingabe durch die Quadratwurzel von 2 und geben Sie das gerundete Ergebnis als Übereinstimmung zurück).

(Die von mir geschriebene Regex-Engine kann hilfreich sein, da sie bei unären mathematischen Regexen sehr schnell ist und einen unären numerischen Modus enthält, mit dem Bereiche natürlicher Zahlen getestet werden können. Sie verfügt jedoch auch über einen Zeichenfolgenmodus, mit dem nicht-unäre oder unäre Regexe ausgewertet werden können Standardmäßig ist es ECMAScript-kompatibel, verfügt jedoch über optionale Erweiterungen (mit denen selektiv Teilmengen von PCRE oder sogar molekularer Lookahead hinzugefügt werden können, was keine andere Regex-Engine hat).

Lesen Sie andernfalls weiter und lesen Sie auch diesen GitHub Gist (Warnung, viele Spoiler), der den Weg des Drängens von ECMAScript-Regex auf natürliche Zahlenfunktionen mit zunehmendem Schwierigkeitsgrad aufzeichnet (beginnend mit Teukon's Puzzlesatz, nicht alle mathematisch), der dies ausgelöst hat Reise).

Wie bei den anderen regulären Ausdrücken für dieses Problem wird die Eingabe als zwei unäre Zahlen angegeben, die durch ein Komma getrennt sind und einen einschließenden Bereich darstellen. Es wird nur eine Nummer zurückgegeben. Der reguläre Ausdruck könnte so modifiziert werden, dass alle Zahlen, die den gleichen kleinsten und größten Primfaktor haben, als separate Übereinstimmungen \Kzurückgegeben werden. Dies erfordert jedoch einen Lookbehind mit variabler Länge und das Einfügen eines Lookahead oder das Zurückgeben des Ergebnisses als Erfassung anstelle einer Übereinstimmung.

Die hier angewandte Technik der wiederholten impliziten Division durch den kleinsten Primfaktor ist identisch mit derjenigen, die in den Match-Zeichenfolgen verwendet wird, deren Länge eine vierte Potenz der Antwort ist, die ich vor einiger Zeit veröffentlicht habe.

Ohne weiteres: ((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$

Sie können es hier ausprobieren.

Und die Freiraumversion mit Kommentaren:

                        # No ^ anchor needed, because this algorithm always returns a
                        # match for valid input (in which the first number is less than
                        # or equal to the second number), and even in /g mode only one
                        # match can be returned. You can add an anchor to make it reject
                        # invalid ranges.

((.+).*),               # \1 = low end of range; \2 = conjectured number that is the
                        # smallest number in the set of the largest prime factor of each
                        # number in the range; note, it is only in subsequent tests that
                        # this is implicitly confined to being prime.
                        # We shall do the rest of our work inside the "high end of range"
                        # number.

(?!                     # Assert that there is no number in the range whose largest prime
                        # factor is smaller than \2.
  .*(?=\1)              # Cycle tail through all numbers in the range, starting with \1.

  (                     # Subroutine (?3):
                        # Find the largest prime factor of tail, and leave it in tail.
                        # It will both be evaluated here as-is, and later as an atomic
                        # subroutine call. As used here, it is not wrapped in an atomic
                        # group. Thus after the return from group 3, backtracking back
                        # into it can increase the value of tail – but this won't mess
                        # with the final result, because only making tail smaller could
                        # change a non-match into a match.

    (                   # Repeatedly divide tail by its smallest prime factor, leaving
                        # only the largest prime factor at the end.

      (?=(..+)(\5+$))   # \6 = tool to make tail = \5 = largest nontrivial factor of
                        # current tail, which is implicitly the result of dividing it
                        # by its smallest prime factor.
      \6                # tail = \5
    )*
  )
  (?!\2)                # matches iff tail < \ 2
)

# now, pick a number in the range whose largest prime factor is \2
.*(?=\1)                # Cycle tail through all numbers in the range, starting with \1.
\K                      # Set us up to return tail as the match.
(?3)                    # tail = largest prime factor of tail
\2$                     # Match iff tail == \2, then return the number whose largest
                        # prime factor is \2 as the match.

Der Algorithmus kann einfach nach ECMAScript portiert werden, indem der Unterprogrammaufruf durch eine Kopie des Unterprogramms ersetzt und die Übereinstimmung als Erfassungsgruppe zurückgegeben wird, anstatt \ K zu verwenden. Das Ergebnis ist 80 Byte lang:

((x+)x*),(?!.*(?=\1)((?=(xx+)(\4+$))\5)*(?!\2)).*(?=\1)(((?=(xx+)(\8+$))\9)*\2$)

Probieren Sie es online!

Beachten Sie, dass ((.+).*)dies geändert werden kann ((.+)+), indem die Größe um 1 Byte (von 66 auf 65 Byte ) verringert wird, ohne dass die korrekte Funktionalität verloren geht. Der reguläre Ausdruck explodiert jedoch exponentiell in der Langsamkeit.

Probieren Sie es online! (79 Byte ECMAScript Exponential-Slow-Down-Version)

Deadcode
quelle
11

Python 2, 95

i=input()
for a in range(*i):
 s=a;p=2
 while~-a:b=a%p<1;p+=1-b;a/=p**b
 if p<i:i=p;j=s                                        
print j

Ermittelt die Glätte der Zahlen durch Versuchsdivision, bis die Zahl 1 ist. iSpeichert die kleinste Glätte, die bisher erreicht wurde, und jspeichert die Zahl, die diese Glätte ergab.

Vielen Dank an @xnor für die Golfplätze.

isaacg
quelle
1
Das if/elsemuss verkürzbar sein. Mein erster Gedanke ist b=a%p<1;p+=1-b;a/=p**b. Oder ein Exec, der einen der beiden Befehle in einer verschachtelten Zeichenfolge ausführt. Funktioniert vielleicht auch while~-a.
Xnor
isaacg - ich liebe diese antwort! Was für eine brillante Art und Weise, nach dem größten Primfaktor zu suchen! Ich habe meine Antwort aktualisiert, um Ihre Methode auszuleihen, wobei Ihnen die Methode gutgeschrieben wurde.
Todd Lehman
Tolle Lösung! Mit s,p=a,2, i,j=p,s, @ xnor Ideen, redundante Vertiefung entfernt und die während der Block in einer Zeile ergibt 95 Zeichen setzen. Nicht sicher, wie Sie auf 98 gekommen sind ...
Falko
Dieser Code ist voll von Emoticons :)
Rosenthal
@Falko diese beiden Änderungen speichern keine Zeichen. 7-> 7.
isaacg
10

J, 22 20 19 Zeichen

({.@/:{:@q:)@(}.i.)

Z.B

   2001 ({.@/: {:@q:)@(}. i.) 2014
2002

(Funktionen, die zwei Argumente annehmen, sind in J angefügt.)

FireFly
quelle
Ich hatte auch einen Riss, kam nicht so kurz wie diese Antwort. Noch:(#~ (= <./)@:(i:"1&1)@:*@:(_&q:))@:([ + i.@-~)
--ıɐɔuʇǝɥʇs
Hier {:ist das gleiche wie >./und spart 1 Byte.
Randomra
@randomra Du hast recht - guten Ruf!
FireFly
Schön. TIO, wenn Sie es hinzufügen möchten: Probieren Sie es online!
Jonah
9

Haskell, 96 94 93 86 80 Zeichen

x%y|x<2=y|mod x y<1=div x y%y|0<1=x%(y+1)
a#b=snd$minimum$map(\x->(x%2,x))[a..b]

Nutzung über GHCi (eine Haskell-Shell):

>5 # 9
8
>9 # 15
9

EDIT: jetzt ein viel einfacherer Algorithmus.

Diese Lösung enthält beide Zahlen im Bereich (also 8 # 9und 7 # 8sind beide 8)

Erläuterung:

Die (%) Funktion akzeptiert zwei Parameter, x und y. Wenn y 2 ist, gibt die Funktion die Glätte von x zurück.

Der Algorithmus von hier ist einfach: Ermittelt die kombinierte Liste aller Glättungen von Zahlen in der Eingabe, wobei jede Glättung einen Verweis auf ihre ursprüngliche Nummer speichert, sortiert dann, um die kleinste zu erhalten, und gibt die referenzierte Nummer zurück.


Hier ist eine ungolfed Javascript-Version mit dem gleichen Algorithmus:

function smoothness(n,p)
{
    p = p || 2
    if (x == 1)
        return p
    if (x % p == 0)
        return smoothness(x/p, p)
    else
        return smoothness(x,p+1);
}
function smoothnessRange(a, b)
{
    var minSmoothness = smoothness(a);
    var min=a;
    for(var i=a+1;i <= b;i++)
        if(minSmoothness > smoothness(i))
        {
            minSmoothness = smoothness(i)
            min = i
        }
    return min;
}
stolzer haskeller
quelle
Wäre es möglich, den Alias ​​auf ein Minimum zu verkürzen? Das sieht so aus, als würde es einige Zeichen speichern.
isaacg
Ich habe es versucht, aber wegen der Monomorphismusbeschränkung kostet es tatsächlich einen Charakter
stolzen Haskeller
Sie können nicht einfach m = Minimum tun? Haskell ist immer noch ein Rätsel.
isaacg
1
@isaacg Um die Monomorphismus-Beschränkung zu umgehen, müsste man schreibenm l=minimum l
stolzer Haskeller
2
Ich wollte eine Haskell-Lösung posten, bis ich deine sah, die sogar meine unvollständige Version
übertrifft
9

Mathematica, 61 45 39 Zeichen

Range@##~MinimalBy~Last@*FactorInteger&

Sehr einfache Implementierung der Spezifikation als unbenannte Funktion.

  • Holen Sie sich das Sortiment (inklusive).
  • Alle ganzen Zahlen berücksichtigen.
  • Finden Sie das Minimum, sortiert nach dem größten Primfaktor.
Martin Ender
quelle
8

Lua - 166 Zeichen

Ich nicht habe (noch!) Genug Ruf zu kommentieren AndoDaan Lösung , aber hier sind einige Verbesserungen an seinem Code

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d<1 do f[#f+1]=d n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Änderungen :

  • Die n%d==0durch n%d<1die in diesem Fall äquivalent ist ,
  • Leerzeichen entfernt
  • Ersetzt table.insert(f,d)durch f[#f+1]=d ( #fist die Anzahl der Elemente von f)
Adriweb
quelle
Ah, ich bin froh, dass ich hierher geschaut habe. Ah, die ersten beiden hätte ich überprüfen und erwischen sollen, aber deine dritte Verbesserung ist neu für mich (ich meine nur anders als ich es gewohnt bin). Das wird mir hier und da auf golf.shinh.com sehr helfen. Vielen Dank!
AndoDaan
8

Bash + Coreutils, 56 Bytes

seq $@|factor|sed 's/:.* / /'|sort -nk2|sed '1s/ .*//;q'

Die Eingabe stammt von genau zwei Befehlszeilenargumenten (Danke @ nyuszika7h !!!). Die Ausgabe ist ein einzelnes Ergebnis, das an STDOUT ausgegeben wird.

  • seq Liefert den Zahlenbereich (eine pro Zeile) aus den Befehlszeilenargumenten.
  • factorLiest diese Zahlen und gibt jede Zahl aus, gefolgt von einem Doppelpunkt und der sortierten Liste der Primfaktoren dieser Zahl. Der größte Primfaktor steht also am Ende jeder Zeile.
  • Der erste sedentfernt den Doppelpunkt und alle bis auf den letzten / größten Primfaktor, sodass eine Liste mit jeder Zahl (Spalte 1) und ihrem größten Primfaktor (Spalte 2) verbleibt.
  • sort numerisch in aufsteigender Reihenfolge durch die Spalte 2.
  • Die letzte sedÜbereinstimmung mit Zeile 1 (Nummer, deren größter Primfaktor der kleinste in der Liste ist) entfernt alles, einschließlich und nach dem ersten Leerzeichen, und wird dann beendet. seddruckt das Ergebnis dieser Ersetzung vor dem Beenden automatisch aus.

Ausgabe:

$ ./smooth.sh 9 15
12
$ ./smooth.sh 9 16
16
$ ./smooth.sh 157 249
162
$ ./smooth.sh 2001 2014
2002
$ 

Hinweis Bereiche sind in diesem Zusammenhang einschließlich der beiden Endpunkte.

Digitales Trauma
quelle
1
seq $@ist 3 Bytes kürzer, wenn Sie davon ausgehen können, dass es nur zwei Argumente gibt.
Nyuszika7h
@ nyuszika7h Schöne Idee - danke!
Digital Trauma
5

Python 2, 67

f=lambda R,F=1,i=2:[n for n in range(*R)if F**n%n<1]or f(R,F*i,i+1)

Das Nachdenken über ein anderes Golfspiel brachte mich auf die Idee, einen neuen Algorithmus zur Überprüfung der Glätte zu entwickeln, daher die späte Antwort.

Die Primfaktorisierung der Fakultät i!umfasst höchstens genau die Primzahlen i. Wenn nes sich also um ein Produkt mit unterschiedlichen Primzahlen handelt, ist seine Glätte (der größte Primfaktor) der kleinste, ifür den nein Teiler von ist i!. Um wiederholte Primfaktoren zu berücksichtigen n, können wir stattdessen eine ausreichend hohe Potenz von verwenden i!. Insbesondere (i!)**ngenügt.

Der Code versucht, die Fakultäten zu erhöhen F=i!und aktualisiert sie rekursiv. Wir filtern nach den Teilern von Fim Eingabebereich und geben sie aus, falls vorhanden, und gehen ansonsten zu über (i+1)!.

Testfall:

>> f([157, 249])
[162, 192, 216, 243]
xnor
quelle
4

C  149,   95

Bearbeitete Antwort:

Ich kann für diese Lösung keine Gutschrift verlangen. Diese aktualisierte Antwort leiht die schöne Methode aus, die isaacg in seiner Python-Lösung verwendet. Ich wollte sehen , ob es möglich war , es als verschachtelte in C zu schreiben for/ whileSchleife ohne geschweifte Klammern, und es ist!

R(a,b,n,q,p,m){for(;a<b;m=p<q?a:m,q=p<q?p:q,n=++a,p=2)while(n>1)if(n%p)p++;else n/=p;return m;}

Erläuterung:

  • Die Funktion R(a,b,n,q,p,m)durchsucht den Bereich abis b-1und gibt die erste gefundene glatte Zahl zurück. Invocation erfordert die Einhaltung der folgenden Form: R(a,b,a,b,2,0)so daß die Variablen innerhalb der Funktion effektiv initialisiert werden , wie folgt: n=a;q=b;p=2;m=0;.

Ursprüngliche Antwort :

Dies war meine ursprüngliche Antwort ...

P(n,f,p){for(;++f<n;)p=p&&n%f;return p;}
G(n,f){for(;--f>1;)if(n%f==0&&P(f,1,1))return f;}
R(a,b,p,n){for(;++p;)for(n=a;n<b;n++)if(G(n,n)==p)return n;}

Erläuterung:

  • Die Funktion P(n,f,p)prüft den Wert nauf Primalität und gibt true (ungleich null) zurück, wenn nes sich um eine Primzahl handelt, oder false (null), wenn nes sich nicht um eine Primzahl handelt. fund pmüssen beide als 1 übergeben werden.
  • Die Funktion G(n,f)liefert den größten Primfaktor von n. fmuss als übergeben werden n.
  • Die Funktion R(a,b,p,n)durchsucht den Bereich abis b-1und gibt die erste gefundene glatte Zahl zurück. pmuss übergeben werden, da 1. nein beliebiger Wert sein kann.

Testfahrer:

test(a,b){printf("smooth_range(%d, %d)\n%d\n",a,b,S(a,b,1,0));}
main(){test(5,11);test(9,16);test(9,17);test(157,249);test(2001,2014);}

Ausgabe:

smooth_range(5, 11)
8
smooth_range(9, 16)
9
smooth_range(9, 17)
16
smooth_range(157, 249)
162
smooth_range(2001, 2014)
2002
Todd Lehman
quelle
Ich würde behaupten, dies verstößt gegen die Klausel "Keine Kodierung zusätzlicher Informationen in der Eingabe".
Alchymist
@Alchymist - Sie mögen Recht haben ... aber ich glaube nicht, dass die Pseudo-Argumente wirklich zusätzliche Informationen enthalten. Zumindest keine Informationen, die einen Hinweis auf die Antwort geben.
Todd Lehman
4

Haskell - 120

import Data.List
import Data.Ord
x!y=(minimumBy(comparing(%2)))[x..y]
x%y|x<y=y|x`mod`y==0=(x`div`y)%y|otherwise=x%(y+1)

Anwendungsbeispiel:

> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002
Taylor Fausak
quelle
1
Könnten Sie nicht <1anstelle von verwenden ==0?
5.
Ja, das wäre eine schöne Verbesserung. Es gibt viele kleine Dinge, die man besser machen könnte. Zum Glück hat diese Antwort schon alle: codegolf.stackexchange.com/a/36461
Taylor Fausak
4

Q, 91 Zeichen K, 78 Zeichen

{(x+{where x=min x}{(-2#{x div 2+(where 0=x mod 2_til x)@0}\[{x>0};x])@0}'[(x)_til y+1])@0}

k würde wahrscheinlich ein Dutzend Charaktere rasieren

edit: in der Tat, diesmal die obere Schranke als nicht inklusive behandeln

{*:x+{&:x=min x}{*:-2#{6h$x%2+*:&:x={y*6h$x%y}[x]'[2_!x]}\[{x>0};x]}'[(x)_!y]}
Arthur B
quelle
4

Hinweis: Diese Antwort ist nicht zulässig.

Diese Antwort verwendet mehrere Funktionen von Pyth, die hinzugefügt wurden, nachdem die Herausforderung gestellt wurde.

Ich habe eine weitere neue Funktion hinzugefügt, die unären Bereich für ein 2-Element-Tupel aufruft, wodurch die Lösung um zwei Zeichen verkürzt wird:

Pyth , 7

hoePNUQ

Die Eingabe erfolgt nun kommagetrennt. Der Rest ist der gleiche.


Diese Antwort verwendet eine Funktion von Pyth, die hinzugefügt wurde, nachdem diese Frage gestellt wurde, insbesondere nachdem @ aditsus wunderbare CJam-Lösung angezeigt wurde. Davon abgesehen wollte ich demonstrieren, was das Hinzufügen dieser Funktion ermöglicht hat. Das Merkmal ist P, dass es sich um eine Arity-1-Funktion handelt , die bei einer Ganzzahleingabe eine Liste aller Primfaktoren der Eingabe zurückgibt, sortiert von klein nach groß.

Pyth , 9

hoePNrQvw

Verwendet Bereiche im Python-Stil, wobei die Zeilenumbrüche in STDIN getrennt sind. Gibt die kleinste Lösung an STDOUT aus.

Erläuterung:

      Q = eval(input())                         Implicit, because Q is present.
h     head(                                     First element of
 o         order_by(                            Sort, using lambda expression as key.
                    lambda N:                   Implicit in o
  e                          end(               Last element of
   PN                            pfact(N)),     List containing all prime factors of N.
  r                 range(                      Python-style range, lower inc, upper exc.
   Q                      Q,                    A variable, initialized as shown above.
   vw                     eval(input()))))      The second entry of the range, same way.

Tests:

$ newline='
'

$ echo "9${newline}16" | ./pyth.py -c 'hoePNrQvw'
9

$ echo "9${newline}17" | ./pyth.py -c 'hoePNrQvw'
16

$ echo "157${newline}249" | ./pyth.py -c 'hoePNrQvw'
162

$ echo "2001${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002
isaacg
quelle
@ MartinBüttner Yep, wie aus seinem Kommentar zur CJam-Lösung hervorgeht
Adriweb
@ MartinBüttner Ja, P, ist das neue Feature. Ich werde das in die Antwort setzen.
Isaacg
1
Erlaubt oder nicht, nicht nur, dass es mir gefällt, sondern ich denke auch, dass diese kurzen "Makros" lesbar sind, wenn Sie darauf achten - sie konvertieren schließlich zu einfachem Python. Für eine Golfsprache muss etwas gesagt werden, die gut für das Golfspiel ist, aber nicht unbedingt verschleiert.
Kuba Ober
@KubaOber Danke, Kuba. Das war schon immer meine Absicht, Pyth zu schreiben, um es so lesbar wie möglich zu machen. Ich bin froh, dass es funktioniert.
isaacg
3

Lua - 176 Zeichen

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d==0 do table.insert(f, d)n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Ich sollte aufhören in Lua zu golfen. Es hat keinen Sinn.

AndoDaan
quelle
14
Meiner Meinung nach ist Code-Golf wie Boxen: Es gibt Gewichtsklassen. Eine bestimmte Sprache gewinnt vielleicht nicht sofort, aber es macht Spaß und ist aufschlussreich, in dieser Klasse / Sprache Golf zu spielen.
Michael Easter
3

Clojure - 173 170 Zeichen

Ich bin ein Clojure-Neuling. Golf gespielt:

(defn g[x,d](if(and(= 0(mod x d))(.isProbablePrime(biginteger d) 1))d 0))(defn f[i](apply max-key(partial g i)(range 2(inc i))))(defn s[a,b](first(sort-by f(range a b))))

Probeläufe:

Bereiche schließen das untere Ende ein, schließen das obere Ende aus: [a, b) Druckt nur eine der glattesten Zahlen, wenn mehrere auftreten.

(println (s 5 11))
(println (s 9 16))
(println (s 9 17))
(println (s 157, 249))
(println (s 2001, 2014))

ergibt:

bash$ java -jar clojure-1.6.0.jar range.clj
8
9
16
192
2002

Ungolfed:

(defn g [x,d] (if (and (= 0(mod x d)) (.isProbablePrime (biginteger d) 1)) d 0))
(defn f [i] (apply max-key (partial g i) (range 2 (inc i))))
(defn s [a,b] (first (sort-by f (range a b))))
Michael Easter
quelle
1
Ein Bereich, der das untere Ende und das obere Ende ausschließt, wird normalerweise geschrieben [a, b).
murgatroid99
Ja, danke für den Hinweis
Michael Easter
3

Ruby, 65 62

require'prime'
s=->a,b{(a..b).min_by{|x|x.prime_division[-1]}}

Mit Entschuldigung an https://codegolf.stackexchange.com/a/36484/6828 , ist dies die Golfversion (und etwas vereinfacht) davon. Verwendet einen inklusiven Bereich, da dieser ein Zeichen kürzer ist.

1.9.3-p327 :004 > s[157,249]
 => 192 
1.9.3-p327 :005 > s[5,11]
 => 8 
1.9.3-p327 :006 > s[9,15]
 => 12 
1.9.3-p327 :007 > s[9,16]
 => 16 

Und danke an YenTheFirst für das Speichern von drei Zeichen.

Histokrat
quelle
1
Sie können tatsächlich ohne die [0] davonkommen, da der Array-Vergleich dem ersten Element ohnehin Priorität einräumt. Dies führt zu unterschiedlichen, aber dennoch korrekten Ergebnissen.
YenTheFirst
3

C # LINQ: 317 303 289 262

using System.Linq;class P{static void Main(string[]a){System.Console.Write(Enumerable.Range(int.Parse(a[0]),int.Parse(a[1])).Select(i=>new{i,F=F(i)}).Aggregate((i,j)=>i.F<j.F?i:j).i);}static int F(int a){int b=1;for(;a>1;)if(a%++b<1)while(a%b<1)a/=b;return b;}}

Ungolfed:

using System.Linq;

class P
{
  static void Main(string[]a)
  {
    System.Console.Write(
      Enumerable.Range(int.Parse(a[0]), int.Parse(a[1])) //create an enumerable of numbers containing our range (start, length)
        .Select(i => new { i, F = F(i) }) //make a sort of key value pair, with the key (i) being the number in question and the value (F) being the lowest prime factor
        .Aggregate((i, j) => i.F < j.F ? i : j).i); //somehow sort the array, I'm still not entirely sure how this works
  }
  static int F(int a)
  {
    int b=1;
    for(;a>1;)
      if(a%++b<1)
        while(a%b<1)
          a/=b;
    return b;
  }
}

Es nimmt den Start und die Länge von der Kommandozeile auf und gibt die größte glatte Zahl zurück.

Ich habe Antworten von hier und hier verwendet , um meine Antwort zu geben.

Vielen Dank an VisualMelon für die Optimierung und die Reduzierung von 12 Byte! Ich habe auch die geschweiften Klammern beim Speichern von 2 Bytes entfernt, und CodeInChaos hat auf einige offensichtliche Dinge hingewiesen, die ich übersehen habe (nochmals vielen Dank).

Verdammt
quelle
Neben einigen Kleinigkeiten für allgemeine Zwecke können Sie 4 Bytes einsparen, Findem Sie int bneben m definieren. In ein paar Orte führen Sie den Vergleich a%b==0, und aund bsind immer positiv , dass Sie ein Byte für jede durch Überprüfung schneiden kann , wenn es weniger ist als 1 a%b<1. Sie können ein Byte auch speichern, indem Sie bdie if-Bedingung inkrementieren a%++b<0und nicht die for -Bedingung, indem Sie es auf 1 initialisieren. Ich denke auch, dass es in diesem Fall billiger ist, System.Console.WriteLinedie namespaceKlausel nur vollständig zu qualifizieren und zu vermeiden .
VisualMelon
@VisualMelon Dank, aktualisiert mit Ihren Ideen :)
ldam
Das m=...:m;Ding fällt außerhalb der while-Schleife. Daher können Sie die Drop m=0,und ersetzen return m;mit return m=b>m?b:m;. Dann kannst du das m=...:m;ganz fallen lassen.
Tomsmeding
Es mag seltsam klingen, aber dies ist - für mich - weniger redbar als CJam und J. Ich denke, C # wurde so konzipiert, dass es ausführlich ist, und Versuche, es weniger zu machen, machen es unleserlich? Hmm ....
Kuba Ober
Nein, ich stimme zu, LINQ sieht aus wie ein Dämon, wenn man es nur hier und da sieht und nie selbst damit spielt. Sobald Sie es jedoch verstanden haben, ist es wirklich cool :) Trotzdem verstehe ich immer noch nicht ganz, wie es Aggregatefunktioniert. Ich habe es nur versucht, nachdem ich es in einer anderen Antwort gesehen habe, um zu meinem neuen Objekt zu gelangen, anstatt nur zu einem Feld darin es hat einfach perfekt funktioniert :)
ldam
2

R 83

library(gmp)
n=a:b
n[which.min(lapply(lapply(lapply(n,factorize),max),as.numeric))]

Wobei der untere Rand des Eingabebereichs aund der obere Rand (einschließlich) zugeordnet sind b.

gmpist ein Paket, das auf CRAN verfügbar ist. Es fühlte sich schmutzig an, bis ich diese absurde mfFunktion in CJam sah. Installieren Sie durch Eingabe install.packages("gmp")in der Konsole.

Shadowtalker
quelle
1
Wenn Sie lapply3-mal verwenden, möchten Sie es möglicherweise aliasen (dh l=lapplyund dann verwenden l(...). In ähnlicher Weise können Sie, da dies factorizedie einzige Funktion ist, die Sie aus dem Paket gmpverwenden, gmp::factorizeanstatt die Bibliothek zu laden und dann zu verwenden factorize. Ihr Code würde also werden, l=lapply;n=a:b;n[which.min(l(l(l(n,gmp::factorize),max),as.numeric))]die 69 Bytes ist.
Plannapus
2

PowerShell - 85

($args[0]..$args[1]|sort{$d=2
while($_-gt1){while(!($_%$d)){$m=$d;$_/=$d}$d++}$m})[0]

Dadurch wird ein Bereich von Zahlen (einschließlich) basierend auf dem maximalen Primfaktor jeder Zahl sortiert. Es wird das niedrigste sortierte Element zurückgegeben.

> smooth 5 10
8
> smooth 9 15
12
> smooth 9 16
16
> smooth 157 248
243
> smooth 2001 2013
2002
Rynant
quelle
2

J - 16 Zeichen

Verwenden des Bereichsstils ( Start , Länge ), wie in den Kommentaren angegeben.

(0{+/:{:@q:@+)i.

Um als dyadisches Verb verwendet zu werden: linkes Argument ist Start , recht ist Länge .

   5 (+)i. 6              NB. range
5 6 7 8 9 10
   5 (q:@+)i. 6           NB. prime factorizations
5 0 0
2 3 0
7 0 0
2 2 2
3 3 0
2 5 0
   5 ({:@q:@+)i. 6        NB. largest prime factors
5 3 7 2 3 5
   5 (+/:{:@q:@+)i. 6     NB. sort range by smallest factors
8 6 9 5 10 7
   5 (0{+/:{:@q:@+)i. 6   NB. take first entry
8
   f=:(0{+/:{:@q:@+)i.    NB. can also be named
   2001 f 13
2002

Eine ( Start- , End- ) Lösung ist +2 Zeichen und schließt das Ende aus. einschließlich des Endes ist +2 mehr. Aber auf der positiven Seite sieht es ziemlich gut aus, da wir alle {Klammern} zusammenpassen.

(0{}./:{:@q:@}.)i.    NB. excluding
(0{}./:{:@q:@}.)1+i.  NB. including
algorithmshark
quelle
2

Im Ernst, 8 * 14/7 = 16 (nicht wettbewerbsfähig)

,x;`yM`M;m@í@E

Ernsthaft wurde nach dieser Herausforderung erstellt, aber ich wollte diese Antwort posten, weil sie beispielhaft für die Art der Herausforderungen ist, bei denen Ernsthaft gut ist.

Probieren Sie es online!

Erläuterung:

,x;`yM`M;m@í@E
,x;             make two copies of range(a,b) (a,b = input())
   `  `M;       make two copies of the result of the map:
    yM            push maximum prime factor
         m@í    push index of minimum element from prime factors
            @E  push element from range with given index
Mego
quelle
2

Pyth , 7 Bytes

.mePbrF

Probieren Sie es hier aus!

[a,b)[a,b]}r

.mePbrF – Full program with arguments a and b.
     rF – Fold by half-inclusive range. Yields the integers in [a, b).
.m      – Values b in that list which give minimal results when applied f.
  ePb   – function / block f. 
   Pb   – Prime factors of b.
  e     – Last element. This is guaranteed to yield the largest, as they're sorted.
Mr. Xcoder
quelle
1

Cobra - 150

def f(r as vari int)
    x,y=r
    c,o=y,0
    for n in x:y,for m in n:0:-1
        p=1
        for l in 2:m,if m%l<1,p=0
        if n%m<=0<p
            if m<c,c,o=m,n
            break
    print o

Ich bin mir nicht mal sicher, warum ich mich die Mühe gemacht habe, Cobra kann hier einfach nicht mithalten.

Οurous
quelle
1
Cobra sieht aus wie Python ... Was sind die Unterschiede?
Beta-Zerfall
@BetaDecay Cobra ist das, was passiert, wenn Sie C # die Syntax von Python geben. The Cobra Website
--urous
1

Ruby - 113 Zeichen

Verwenden der Stdlib. Gibt ein Ergebnis zurück. Getestet auf Rubin 2.1.2.

require 'prime'
def smooth_range(a,b)
  (a...b).sort_by{|e|e.prime_division.flat_map{|f,p|[f]*p}.uniq.max}[0]
end
John P. Terry
quelle
1
Willkommen bei Programmierpuzzles und Code Golf Stack Exchange. Vielen Dank für die Veröffentlichung Ihres Ergebnisses. Da es sich um eine Code-Golf-Frage handelt, geben Sie in Ihrer Antwort bitte die Anzahl der Zeichen an. Sie können ein Tool wie dieses verwenden: javascriptkit.com/script/script2/charcount.shtml
isaacg
1

Perl (5,10+), 83

for(<>..<>){$n=$_;$p=2;$_%$p&&$p++or$_/=$p while$_>1;$m=$p,$r=$n if$p<$m||!$m}
say$r

(Zeilenumbruch kann entfernt werden). Nimmt zwei Endpunkte eines Inklusivbereichs in zwei Standardzeilen auf (weil dies <>billiger ist als der Zugriff ARGV) und gibt die glatteste bis standardmäßige Ausgabe aus. Wenn es eine Gleichheit für glattestes gibt, druckt das kleinste. Könnte das größte auf Kosten eines Zeichens drucken.

Der Algorithmus ist im Grunde der Weg von isaacg, den größten Primfaktor zu finden, obwohl wir ihn unabhängig gefunden haben. Dieser Teil lässt sich wunderbar zu einer einzigen Aussage in Perl zusammenfassen, der Rest hat mehr Overhead als ich gerne hätte.

Sollte unter perl -Eoder mit einer use 5.012Präambel ausgeführt werden. Wenn Sie das nicht können, ersetzen Sie say$rdurch print$r,$/.

hobbs
quelle
1

Python 2 (84)

f=lambda n,p=2:n>1and f(n/p**(n%p<1),p+(n%p>0))or p
print min(range(*input()),key=f)

@ isaacgs Lösung , aber mit einer Nach-min Funktionstaste anstelle einer expliziten Min-Suche und einer rekursiven Funktion, die die Rolle der Iteration spielt.

Führen Sie Stackless Python aus , um Rekursionsbeschränkungen zu vermeiden.

Es sieht verschwenderisch aus, den eingeklammerten Zustand zu verwenden (n%p<1)und dann seine Verneinung auch in Klammern zu wiederholen (n%p>0), aber das war das Beste, was ich bekommen habe. Ich habe ein paar Dinge ausprobiert, aber sie sind schlimmer geworden.

f(n/p**(n%p<1),p+(n%p>0))     # Current for comparison
f(*[n/p,n,p,p+1][n%p>0::2])
n%p and f(n,p+1)or f(n/p,p)
f(*n%p and[n,p+1]or[n/p,p])

Ich freue mich über jede Verbesserung, die Sie sich vorstellen können.

xnor
quelle
1

Java 8 - 422 454 Zeichen

Ich lerne Java 8 und wollte dies in Bezug auf Java (oder sogar Java 8-Streams) ausprobieren.

Im Vergleich zu anderen Sprachen ist dies eine brutale, aber interessante Übung.

Golf gespielt:

import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}

Ungolfed:

import java.util.stream.*;
import java.math.*;

class F {
    int v;
    int i;
    public int getV() { return v; }
    F (int i) { 
        this.i = i;
        v = IntStream.range(2,i+1)
                     .map( j -> ((i%j==0) && 
                           new BigInteger(""+j).isProbablePrime(1))?j:0)
                     .max()
                     .getAsInt();
    }
}

public class T {
    int s(int a, int b) {
        return IntStream.range(a,b+1)
                    .boxed()
                    .map(F::new)
                    .sorted(java.util.Comparator.comparingInt(F::getV))
                    .collect(java.util.stream.Collectors.toList())
                    .get(0).i;
    }
}

Beispiellauf mit:

public static void main(String[] s) {
    System.out.println(new T().s(157,249));
}

192
Michael Easter
quelle
1

MATL ( nicht konkurrierend ), 20 Bytes

Diese Sprache wurde nach der Herausforderung entworfen

Die Reichweite ist an beiden Enden inklusive. Die Zahlen werden als zwei separate Eingänge verwendet.

2$:t[]w"@YfX>v]4#X<)

Probieren Sie es online!

Erläuterung

2$:          % implicitly input two numbers. Inclusive range
t            % duplicate                      
[]           % empty array
w            % swap elements in stack         
"            % for each                  
  @          %   push loop variable
  Yf         %   prime factors                  
  X>         %   maximum value
  v          %   vertical concatenation         
]            % end for each                         
4#X<         % arg min 
)            % index with this arg min into initial range of numbers
Luis Mendo
quelle
Ich denke heute wären das 17 Bytes &:[]y"@YfX>h]&X<)oder vielleicht 16 :[]y"@YfX>h]&X<). Das war &wirklich eine großartige Idee (und ich vermute, dass es ydamals noch keine gab?).
Sundar
Und es sieht so aus, als ob eine Sendung Yfmit vorangestellten Einsen auch hier nützlich gewesen wäre, aber das reicht wahrscheinlich nicht aus, um zu entscheiden, dass es eine gute Idee im Allgemeinen ist. :)
Sundar
Ja, das war der Anfang, also nein yoder &. Wir danken Suever für die sehr nützliche Semantik des letzteren (meine ursprüngliche Idee war, es als "eine Eingabe mehr als Standard" zu bezeichnen). Wenn wir mehr Fälle sehen, in denen das YfHinzufügen von solchen nützlich wäre, kann es sich lohnen, diese Funktion hinzuzufügen. Das Problem ist, dass es ungefähr 34 Antworten gibt, die Yf(gemäß diesem Skript ) verwendet werden, so dass es schwer zu sagen ist
Luis Mendo
1

Jelly , 7 Bytes, Punktzahl = 7 ÷ 7 × 8 = 8, Herausforderung nach den Sprachdaten

rÆfṀ$ÐṂ

Probieren Sie es online!

Nimmt die Endpunkte für den unteren und oberen Bereich als zwei separate Argumente. Gibt eine Liste aller glattesten Nummern im Bereich aus. (Dies kann als Funktion betrachtet werden. In diesem Fall handelt es sich bei der Ausgabe um eine Jelly-Liste oder um ein vollständiges Programm. In diesem Fall verwendet die Ausgabe dieselbe Listendarstellung wie JSON.)

Erläuterung

In Zeiten, in denen Ihr Jelly-Programm nur eine wörtliche Übersetzung der Spezifikation ist…

rÆfṀ$ÐṂ
r        Range from {first argument} to {second argument}
     ÐṂ  Return the elements which have the minimum
   Ṁ$      largest
 Æf          prime factor

quelle