Twoim zadaniem jest znalezienie najbardziej płynnej liczby w danym zakresie. Innymi słowy, znajdź liczbę, której największy czynnik pierwszy jest najmniejszy.

Liczba gładka to taka, której największy czynnik pierwszy jest niewielki. Liczby tego typu są przydatne do szybkiego algorytmu transformacji Fouriera, kryptoanalizy i innych aplikacji.

Na przykład, powyżej zakresu 5, 6, 7, 8, 9, 10, liczba 8 jest najbardziej płynną liczbą, ponieważ największa liczba pierwsza 8 wynosi 2, podczas gdy wszystkie inne liczby mają liczbę pierwszą 3 lub większą.

Dane wejściowe: danymi wejściowymi będą dwie dodatnie liczby całkowite, które określają zakres. Minimalna dopuszczalna liczba całkowita w zakresie to 2. Możesz wybrać, czy zakres jest obejmujący, wyłączny, częściowo wyłączny itp., O ile można określić dowolny zakres w granicach twojego języka. Możesz przyjmować liczby za pomocą funkcji wprowadzania, standardowego wejścia, argumentu wiersza poleceń lub dowolnej równoważnej metody dla swojego języka. Brak kodowania dodatkowych informacji na wejściu.

Wyjście: Zwraca, drukuje lub odpowiada jednej lub więcej liczb całkowitych w zakresie wejściowym, które są maksymalnie gładkie (minimalny największy współczynnik). Zwracanie wielu wyników jest opcjonalne, ale jeśli zdecydujesz się to zrobić, wyniki muszą być wyraźnie rozdzielone. Natywny format wyjściowy jest odpowiedni dla wielu wyników.

W odpowiedzi proszę podać, w jaki sposób przyjmujesz dane wejściowe i dajesz wyniki.

Punktacja: Kod golfa. Policz według znaków, jeśli są zapisane w ASCII, lub 8 * bajtów / 7, jeśli nie w ASCII.

Przypadki testowe:

Uwaga: są to zakresy w stylu Pythona, w tym dolny, ale nie górny. Zmień odpowiednio do swojego programu. Konieczny jest tylko jeden wynik.

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=

Wypróbuj na http://cjam.aditsu.net/

Przykładowe dane wejściowe: 2001 2014
Przykładowe dane wyjściowe:2002

Wyjaśnienie:

q~odczytuje i ocenia dane wejściowe, wypychając 2 liczby ze stosu (powiedzmy min i max)
,powoduje, że tablica [0 1 ... max-1]
>przecina tablicę zaczynając od min, co daje [min ... max-1]
{…}$sortuje tablicę za pomocą bloku, aby obliczyć klucz sortujący,
mfuzyskuje tablicę ze wszystkimi liczbami pierwszymi liczby, w celu
W=uzyskania ostatniego elementu tablicy (W = -1), uzyskując w ten sposób największy czynnik pierwszy, który ma być użyty jako klucz sortujący
0=pobiera pierwszy element (posortowanej) tablicy

Regex ( smak .NET PCRE), 183 129 bajtów

Nie próbuj tego w domu!

To nie jest tak naprawdę pretendent do wygranej. Ale Eric Tressler zasugerował rozwiązanie tego problemu bez regexu i nie mogłem się oprzeć, by spróbować. Może to być możliwe również w PCRE (a nawet krócej, patrz poniżej), ale wybrałem .NET, ponieważ moje rozwiązanie wymaga spojrzenia o dowolnej długości. No to ruszamy:

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

Dane wejściowe są kodowane jako obejmujący przedział rozdzielany przecinkami, gdzie obie liczby są podawane w notacji jednoargumentowej za pomocą 1s. Mecz będzie kończył się S1s, gdzie Sjest najbardziej płynną liczbą w zakresie. Więzy są zrywane na korzyść najmniejszej liczby.

Tak więc drugim przykładem z pytania byłby następujący ciąg znaków (dopasowanie podkreślone)

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

Opiera się na (do tej pory dość znanym) wyrażeniu regularnym sprawdzającym , których odmiany są tam osadzone aż 6 razy.

Oto wersja z odstępami i komentarzami dla tych, którzy chcą wiedzieć, co się dzieje.

# 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

Możesz to przetestować online tutaj . Nie próbuj jednak zbyt dużych nakładów, nie udzielam żadnych gwarancji dotyczących wydajności tego potwora.

Edytować:

Skończyło się na przeniesieniu tego do PCRE (co wymaga tylko dwóch kroków) i skróceniu wyrażenia regularnego o prawie jedną trzecią. Oto nowa wersja:

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

Jest to zasadniczo to samo, z dwiema zmianami:

• PCRE nie obsługuje funkcji lookbehind o dowolnej długości (których użyłem, aby dostać się MINdo grupy 1). Jednak PCREobsługuje, \Kktóra resetuje początek dopasowania do bieżącej pozycji kursora. (?<=^(1+),.*)Staje się więc ^(1+),.*?\K, co już oszczędza dwa bajty.
• Prawdziwe oszczędności pochodzą z funkcji rekurencji PCRE. Właściwie nie używam rekurencji, ale możesz użyć ponownie, (?n)aby dopasować grupę n, podobnie jak wywołanie podprogramu. Ponieważ oryginalne wyrażenie regularne zawierało kod umożliwiający dwukrotne znalezienie największego pierwszego czynnika liczbowego, byłem w stanie zastąpić całą większość drugiego prostym (?2).

Regex (smak PCRE), 66 (65🐌) bajtów

Zainspirowany widząc, że zarówno Martin Ender, jak i jaytea , dwaj geniusze wyrażeń regularnych, napisali regexowe rozwiązania dla tego kodu golfa, napisałem własne od zera. Słynny regex sprawdzania liczby pierwszych nie pojawia się nigdzie w moim rozwiązaniu.

Nie czytaj tego, jeśli nie chcesz, aby zepsuta dla ciebie jakaś magia wyrażenia regularnego. Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie zalecamy rozpoczęcie od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript:

1. _{Dopasuj liczby pierwsze (jeśli jeszcze nie wiesz, jak to zrobić w wyrażeniach regularnych)}
2. _{Dopasuj moce 2 (jeśli jeszcze tego nie zrobiłeś). Lub po prostu przebij się przez Regex Golf , który obejmuje Prime i Powers. Pamiętaj, aby wykonać zarówno zestawy problemów Classic, jak i Teukon.}

3. _{Znajdź najkrótszy sposób dopasowania mocy N, gdzie N jest pewną stałą (tzn. Określoną w wyrażeniu regularnym, a nie wejściowym), która może być złożona (ale nie jest wymagana). Na przykład dopasuj moc 6.}

4. _{Znajdź sposób dopasowania N-tych mocy, gdzie N jest pewną stałą> = 2. Na przykład dopasuj idealne kwadraty. (W celu rozgrzewki dopasuj główne moce .)}

5. _{Dopasuj prawidłowe instrukcje mnożenia. Dopasuj liczby trójkątne.}

6. _{Dopasuj liczby Fibonacciego (jeśli jesteś tak szalony jak ja), lub jeśli chcesz trzymać się czegoś krótszego, dopasuj poprawne stwierdzenia potęgowania (dla rozgrzewki, wróć jako logarytm do podstawy 2 potęgi 2 - bonus, zrób to samo dla dowolnej liczby, zaokrąglając ją, jak chcesz) lub liczb silni (dla rozgrzewki, dopasuj liczby pierwotne ).}

7. _{Dopasuj obfite liczby (jeśli jesteś tak szalony jak ja)}

8. _{Oblicz liczbę niewymierną do żądanej precyzji (np. Podziel dane wejściowe przez pierwiastek kwadratowy z 2, zwracając zaokrąglony wynik jako dopasowanie)}

_{(Silnik wyrażeń regularnych, który napisałem, może być pomocny, ponieważ jest bardzo szybki przy jednoargumentowych wyrażeniach matematycznych i zawiera jednoargumentowy tryb liczbowy, który może testować zakresy liczb naturalnych (ale także ma tryb ciągów znaków, który może oceniać wyrażenia jednoargumentowe lub jednoargumentowy z ogranicznikami). Domyślnie jest kompatybilny z ECMAScript, ale ma opcjonalne rozszerzenia (które mogą selektywnie dodawać podzbiory PCRE, a nawet molekularne spojrzenie w przód, coś, czego nie ma żaden inny silnik wyrażenia regularnego).}

W przeciwnym razie czytaj dalej, a także czytaj GistHub Gist (ostrzeżenie, wiele spoilerów), który kronika podróży wypychania wyrażenia regularnego ECMAScript w celu rozwiązania problemów z liczbami naturalnymi o rosnącym stopniu trudności (poczynając od zestawu łamigłówek Teukona, nie wszystkich matematycznych, które wywołały ten problem podróż).

Podobnie jak w przypadku innych regexowych rozwiązań tego problemu, dane wejściowe są podawane jako dwie liczby w jednostajnym bijective, oddzielone przecinkiem, reprezentujące zakres obejmujący. Zwracany jest tylko jeden numer. Wyrażenie regularne można zmodyfikować, aby zwracać wszystkie liczby, które dzielą ten sam najmniejszy największy czynnik główny, jako osobne dopasowania, ale wymagałoby to spojrzenia o zmiennej długości i umieszczenia go \Kw przód lub zwrócenia wyniku jako przechwytywania zamiast dopasowania.

Zastosowana tutaj technika wielokrotnego niejawnego dzielenia przez najmniejszy czynnik pierwszy jest identyczna z tą stosowaną w ciągach Match, których długość jest czwartą odpowiedzią na moc, którą zamieściłem jakiś czas temu.

Bez zbędnych ceregieli: ((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$

Możesz to wypróbować tutaj.

I wersja z wolnym odstępem, z komentarzami:

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

Algorytm można łatwo przenieść do ECMAScript, zastępując wywołanie podprogramu kopią podprogramu i zwracając dopasowanie jako grupę przechwytywania zamiast używania \ K. Wynik ma długość 80 bajtów:

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

Wypróbuj online!

Zauważ, że ((.+).*)można to zmienić ((.+)+), zmniejszając rozmiar o 1 bajt (z 66 do 65 bajtów ) bez utraty poprawnej funkcjonalności - ale wyrażenie regularne eksploduje wolniej.

Wypróbuj online! _{^{(79-bajtowa wersja ECMAScript-spowolnienie wykładnicze)}}

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

Znajduje gładkość liczb według podziału próby, aż liczba będzie iwynosić 1. przechowuje najmniejszą jak dotąd gładkość, jprzechowuje liczbę, która dała tę gładkość.

Dzięki @xnor za golfa.

J, 22 20 19 znaków

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

Na przykład

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

(Funkcje przyjmujące dwa argumenty są niepoprawne w J.)

Haskell, 96 94 93 86 80 znaków

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]

użycie przez GHCi (powłokę Haskell):

>5 # 9
8
>9 # 15
9

EDYCJA: teraz o wiele prostszy algorytm.

to rozwiązanie obejmuje obie liczby z zakresu (więc 8 # 9i 7 # 8są to 8)

wyjaśnienie:

funkcja (%) przyjmuje dwa parametry, xiy. gdy y wynosi 2, funkcja zwraca gładkość x.

algorytm stąd jest prosty - uzyskaj połączoną listę wszystkich gładkości liczb na wejściu z każdą gładkością przechowującą odniesienie do jego oryginalnej liczby, posortuj następnie, aby uzyskać najmniejszą, i zwróć numer odniesienia.

oto wersja javascript bez kodu z tym samym algorytmem:

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

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

Bardzo prosta implementacja specyfikacji jako funkcji bez nazwy.

• Uzyskaj zasięg (włącznie).
• Uwzględnij wszystkie liczby całkowite.
• Znajdź minimum posortowane według największego czynnika pierwszego.

Lua - 166 znaków

I nie nie ma (jeszcze!) Wystarczającą renomę komentować rozwiązania AndoDaan jest , ale tutaj są pewne ulepszenia w swoim kodzie

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)

Zmiany :

• n%d==0Przez n%d<1który odpowiada w tym przypadku
• Usunięto spację
• Zastąpiony table.insert(f,d)przez f[#f+1]=d ( #fto liczba elementów f)

Bash + coreutils, 56 bajtów

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

Dane wejściowe pochodzą z dokładnie dwóch argumentów wiersza polecenia (Thanks @ nyuszika7h !!!). Wyjście jest pojedynczym wynikiem drukowanym do STDOUT.

• seq podaje zakres liczb, po jednej w wierszu, z argumentów wiersza poleceń.
• factorodczytuje te liczby i wypisuje każdą liczbę, a następnie dwukropek i posortowaną listę czynników pierwszych tej liczby. Zatem największy czynnik pierwszy znajduje się na końcu każdej linii.
• Pierwszy sedusuwa dwukropek i wszystkie oprócz ostatniego / największego czynnika pierwszego, więc pozostawia listę każdej liczby (kolumna 1) i jego największy czynnik pierwszy (kolumna 2).
• sort numerycznie w porządku rosnącym według kolumny 2.
• Ostateczne seddopasowanie pierwszej linii (liczba, której największy współczynnik pierwszy jest najmniejszy na liście), usuwa wszystko, łącznie z pierwszą spacją i po niej, a następnie kończy działanie. sedautomatycznie drukuje wynik tej zamiany przed wyjściem.

Wynik:

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

Zakresy notatek w tym kontekście obejmują oba punkty końcowe.

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)

Myślenie o innym golfie dało mi pomysł na nowy algorytm sprawdzania płynności, stąd późna odpowiedź.

Rozkład na czynniki pierwsze i!zawiera maksymalnie co najwyżej liczby pierwsze i. Tak więc, jeśli njest produktem odrębnych liczb pierwszych, jego gładkość (największy czynnik pierwszy) jest najmniejsza, idla której njest dzielnikiem i!. Aby uwzględnić powtarzające się czynniki pierwsze n, możemy zamiast tego użyć wystarczająco wysokiej mocy i!. W szczególności (i!)**nwystarczy.

Kod próbuje zwiększyć silnie F=i!, aktualizowane rekurencyjnie. Filtrujemy dzielniki z Fzakresu wejściowego i wysyłamy je, jeśli istnieją, i w przeciwnym razie przechodzimy do (i+1)!.

Przypadek testowy:

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

C,  149   95

Edytowana odpowiedź:

Nie mogę ubiegać się o kredyt za to rozwiązanie. Ta zaktualizowana odpowiedź zapożycza piękną metodę stosowaną przez isaacga w jego rozwiązaniu Python. Chciałem sprawdzić, czy można napisać w C jako zagnieżdżoną for/ whilepętlę bez nawiasów klamrowych i tak jest!

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

Wyjaśnienie:

• Funkcja R(a,b,n,q,p,m)przeszukuje zakres ado b-1i zwraca pierwszy numer płynność znaleźć. Wywołanie wymaga stosowania się do następującej postaci: R(a,b,a,b,2,0)tak, że zmienne wewnątrz funkcji skutecznie inicjowany w następujący sposób: n=a;q=b;p=2;m=0;.

Oryginalna odpowiedź :

To była moja pierwotna odpowiedź ...

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

Wyjaśnienie:

• Funkcja P(n,f,p)sprawdza wartość pierwszeństwa ni zwraca true (niezerową), jeśli njest liczbą pierwszą, lub false (zero), jeśli nnie jest liczbą pierwszą. fi poba muszą być uznane za 1.
• Funkcja G(n,f)zwraca największy współczynnik pierwszy z n. fnależy przekazać jako n.
• Funkcja R(a,b,p,n)przeszukuje zakres ado b-1i zwraca pierwszy numer płynność znaleźć. pnależy podać jako 1. nmoże być dowolna wartość.

Kierowca testowy:

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

Wynik:

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)

Przykładowe użycie:

> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002

Q, 91 znaków K, 78 znaków

{(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 prawdopodobnie ogoliłby kilkanaście znaków

edycja: rzeczywiście, tym razem traktując górną granicę jako niewłączającą

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

Uwaga: ta odpowiedź jest niedozwolona.

Ta odpowiedź korzysta z wielu funkcji Pyth dodanych po zapytaniu o wyzwanie.

Dodałem kolejną nową funkcję, nazywając jednoargumentowy zasięg w krotce 2-elementowej, co skraca rozwiązanie o dwie postacie:

Pyth , 7

hoePNUQ

Dane wejściowe są teraz oddzielane przecinkami. Reszta jest taka sama.

Ta odpowiedź korzysta z funkcji Pyth, która została dodana po zadaniu tego pytania, szczególnie po obejrzeniu wspaniałego rozwiązania CJam @ aditsu. Biorąc to pod uwagę, chciałem zademonstrować, co umożliwiło dodanie tej funkcji. Jest to funkcja Parity-1, która po wprowadzeniu liczb całkowitych zwraca listę wszystkich czynników pierwszych wejścia, posortowanych od najmniejszej do największej.

Pyth , 9

hoePNrQvw

Wykorzystuje zakresy w stylu Python, nowy wiersz oddzielony na STDIN. Wysyła najmniejsze rozwiązanie do STDOUT.

Wyjaśnienie:

      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.

Testy:

$ 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 znaków

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)

Naprawdę powinienem przestać grać w golfa w Lua. Nie ma sensu.

Clojure - 173 170 znaków

Jestem początkującym Clojure. Gra w golfa:

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

Przykładowe przebiegi:

Zakresy obejmują niskie, z wyłączeniem wyższych: [a, b) Drukuje tylko jedną z najbardziej płynnych liczb, jeśli występuje wiele.

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

daje:

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

Nie golfowany:

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

Przepraszamy za https://codegolf.stackexchange.com/a/36484/6828 , jest to wersja golfowa (i nieco uproszczona). Wykorzystuje zasięg włączający, ponieważ jest on krótszy.

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 

I dzięki YenTheFirst za uratowanie trzech postaci.

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

Nie golfowany:

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

Pobiera początek i długość z wiersza poleceń i zwraca największą liczbę gładką.

Użyłem odpowiedzi tu i tutaj, aby udzielić odpowiedzi.

Dzięki VisualMelon za ulepszenie go i ogolenie 12 bajtów! Pozbyłem się również nawiasów klamrowych w zapisywaniu 2 bajtów, a CodeInChaos wskazał pewne oczywiste rzeczy, za którymi tęskniłem (jeszcze raz dziękuję).

R 83

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

gdzie dolna część zakresu wejściowego jest przypisana, aa górna (włącznie) jest przypisana do b.

gmpto pakiet dostępny w CRAN. Czułem się brudny, dopóki nie zobaczyłem tej absurdalnej mffunkcji w CJam. Zainstaluj, wpisując install.packages("gmp")w konsoli.

PowerShell - 85

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

Spowoduje to posortowanie zakresu liczb (włącznie) na podstawie maksymalnego współczynnika liczby podstawowej dla każdej liczby. Zwraca najniższy posortowany element.

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

J - 16 znaków

Korzystanie ze stylu zakresu ( początkowego , długości ), na co pozwalają komentarze.

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

Używać jako czasownika diademowego: lewy argument to start , prawy to długość .

   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

Rozwiązanie ( początek , koniec ) to +2 znaki i wyklucza koniec; w tym koniec to +2 więcej. Ale z drugiej strony wygląda to całkiem ładnie, ponieważ dopasowujemy wszystkie {nawiasy klamrowe}.

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

Poważnie, 8 * 14/7 = 16 (niekonkurencyjny)

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

Poważnie powstał po tym wyzwaniu, ale chciałem opublikować tę odpowiedź, ponieważ stanowi ona przykład wyzwań, w których poważnie jest dobry.

Wypróbuj online!

Wyjaśnienie:

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

.mePbrF

Wypróbuj tutaj!

$[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.

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

Nie jestem nawet pewien, dlaczego mi przeszkadzało, kobra po prostu nie może tu konkurować.

Rubin - 113 znaków

Używanie stdlib. Zwraca jeden wynik. Testowane na Ruby 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

(podział linii można usunąć). Pobiera dwa punkty końcowe z zakresu obejmującego na dwóch liniach standardowego wejścia (ponieważ <>jest tańszy niż dostęp ARGV) i wysyła sygnał płynniej do standardowego. Jeśli jest krawat dla najbardziej płynnego, drukuje najmniejszy. Można wydrukować największy kosztem jednej postaci.

Algorytm jest w zasadzie sposobem isaacga na znalezienie największego czynnika pierwszego, chociaż wymyśliliśmy go niezależnie. Ta część pięknie gra w golfa do jednego zdania w perlu, reszta ma więcej kosztów ogólnych, niż bym chciał.

Powinien być prowadzony pod perl -Elub z use 5.012preambułą. Jeśli nie można tego zrobić, wymienić say$rsię 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)

Rozwiązanie @ isaacg , ale z minklawiszem funkcyjnym zamiast jawnego wyszukiwania min i funkcją rekurencyjną pełniącą rolę iteracji.

Uruchom w Python bez stosów, aby uniknąć limitów rekurencji.

Używanie sparaliżowanego stanu wydaje się marnotrawstwem (n%p<1), a następnie powtarzanie negacji również w nawiasach (n%p>0), ale to było najlepsze, co dostałem. Próbowałem różnych rzeczy, ale okazały się gorsze.

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

Z zadowoleniem przyjmuję wszelkie ulepszenia, jakie możesz wymyślić.

Java 8 - 422 454 znaków

Uczę się Java 8 i chciałem dać temu szansę w stosunku do Java (a nawet strumieni Java 8).

W porównaniu z innymi językami jest to brutalne, ale ciekawe ćwiczenie.

Gra w golfa:

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

Nie golfowany:

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

przykład uruchom za pomocą:

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

192

MATL ( niekonkurencyjny ), 20 bajtów

Ten język został zaprojektowany po wyzwaniu

Zakres obejmuje na obu końcach. Liczby są traktowane jako dwa osobne dane wejściowe.

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

Wypróbuj online!

Wyjaśnienie

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

Galaretka , 7 bajtów, wynik = 7 ÷ 7 × 8 = 8, wyzwanie postdate języka

rÆfṀ$ÐṂ

Wypróbuj online!

Traktuje punkty końcowe dolnego i górnego zakresu jako dwa osobne argumenty. Wyświetla listę wszystkich najbardziej płynnych liczb w zakresie. (Można to postrzegać jako funkcję, w którym to przypadku wynik jest listą Jelly lub jako pełny program, w którym to przypadku dane wyjściowe używają tej samej reprezentacji listy, co JSON.)

Wyjaśnienie

W tych czasach, gdy Twój program Jelly jest dosłownym tłumaczeniem specyfikacji…

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