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

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

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).

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)}}

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.

J, 22 20 19 Zeichen

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

Z.B

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

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

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

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.

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)

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.

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]

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

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

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]}

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

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.

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))))

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.

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).

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.

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

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

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

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.

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.

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

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,$/.

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.

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

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

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