Ваша задача состоит в том, чтобы найти самое гладкое число в заданном диапазоне. Другими словами, найдите число, у которого наибольший главный фактор наименьший.

Гладкий номер один , чей наибольший простой множитель мал. Числа этого типа полезны для алгоритма быстрого преобразования Фурье, криптоанализа и других приложений.

Например, в диапазоне 5, 6, 7, 8, 9, 108 - это самое гладкое число, потому что наибольшее простое число 8 равно 2, тогда как все остальные числа имеют простое число 3 или больше.

Входные данные: входными данными будут два натуральных числа, которые определяют диапазон. Минимально допустимое целое число в диапазоне - 2. Вы можете выбрать, является ли диапазон включающим, исключительным, полуисключительным и т. Д., Если в пределах вашего языка может быть указан произвольный диапазон. Вы можете получить числа с помощью функции input, stdin, аргумента командной строки или любого другого эквивалентного метода для вашего языка. Нет кодирования дополнительной информации на входе.

Выход: вернуть, вывести или эквивалентно одно или несколько целых чисел во входном диапазоне, которые являются максимально гладкими (минимальный наибольший коэффициент). Возвращать несколько результатов необязательно, но если вы решите это сделать, результаты должны быть четко разграничены. Нативный формат вывода подходит для нескольких результатов.

Пожалуйста, укажите в своем ответе, как вы принимаете вход и даете вывод.

Подсчет очков: код гольфа. Считать по символам, если написано в ASCII, или 8 * байт / 7, если не в ASCII.

Тестовые случаи:

Примечание. Это диапазоны в стиле Python, включая нижний, но не верхний. Измените в соответствии с вашей программой. Нужен только один результат.

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=

Попробуйте это на http://cjam.aditsu.net/

Пример ввода: 2001 2014
Пример вывода:2002

Объяснение:

q~читает и оценивает входные данные, помещая 2 числа в стек (скажем, min и max),
,массив [0 1 ... max-1]
>разбивает массив, начиная с min, что приводит к [min ... max-1]
{…}$сортирует массив, используя блок для вычисления ключа сортировки,
mfполучает массив со всеми простыми множителями числа, по порядку
W=получает последний элемент массива (W = -1), получая, таким образом, наибольший простой множитель, который будет использоваться в качестве ключ сортировки
0=получает первый элемент (отсортированного) массива

Regex ( аромат .NET PCRE), 183 129 байт

Не пытайтесь делать это дома!

Это не совсем претендент на победу. Но Эрик Тресслер предложил решить эту проблему с помощью регулярных выражений, и я не удержался, чтобы попробовать. Это может быть возможно и в PCRE (и даже короче, см. Ниже), но я выбрал .NET, потому что мое решение нуждается в взглядах произвольной длины. Вот так:

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

Входные данные кодируются в виде включенного диапазона через запятую, где оба числа даны в унарной записи с использованием 1s. Матч будет в конце S1, где Sэто самое гладкое число в диапазоне. Галстуки разрываются в пользу наименьшего числа.

Таким образом, вторым примером из этого вопроса будет следующая строка (соответствие подчеркнуто)

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

Он основан на (теперь достаточно известном) регулярном выражении проверки , вариации которого встроены в него 6 раз.

Вот версия, использующая свободное пространство и комментарии для тех, кто хочет знать, что происходит.

# 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

Вы можете проверить это онлайн здесь . Не пытайтесь использовать слишком большие входные данные, я не даю никаких гарантий относительно производительности этого монстра.

Редактировать:

Я закончил тем, что портировал это на PCRE (который требует только двух шагов), и сократил регулярное выражение почти на треть. Вот новая версия:

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

Это по сути то же самое, с двумя изменениями:

• PCRE не поддерживает просмотр назад произвольной длины (который я использовал, чтобы получить MINв группу 1). Тем PCREне менее, есть поддержка, \Kкоторая сбрасывает начало совпадения к текущей позиции курсора. Следовательно (?<=^(1+),.*)становится ^(1+),.*?\K, который уже сохраняет два байта.
• Настоящая экономия достигается благодаря рекурсивной функции PCRE. На самом деле я не использую рекурсию, но вы можете использовать (?n)для сопоставления группы nснова, аналогично вызову подпрограммы. Поскольку исходное регулярное выражение содержало код для нахождения наибольшего простого множителя числа дважды, я смог заменить большую часть второго простым (?2).

Регекс (PCRE аромат), 66 (65🐌) байт

Вдохновленный тем, что Мартин Эндер и jaytea , два гения regex, написали решения regex для этого гольф-кода, я написал свой собственный с нуля. Знаменитое регулярное выражение проверки не появляется нигде в моем решении.

Не читайте это, если вы не хотите испортить вам магию унарных регулярных выражений. Если вы действительно хотите сами разобраться с этой магией, я настоятельно рекомендую начать с решения некоторых проблем в регулярном выражении ECMAScript:

1. _{Подберите простые числа (если вы еще не знакомы с этим в регулярных выражениях)}
2. _{Совпадение степеней 2 (если вы еще этого не сделали). Или просто проложите себе путь через Regex Golf , который включает в себя Prime и Powers. Удостоверьтесь, что делали и классические, и Teukon.}

3. _{Найдите кратчайший способ сопоставления степеней N, где N - некоторая постоянная (то есть указанная в регулярном выражении, а не во входных данных), которая может быть составной (но не обязательной). Например, сопоставьте полномочия 6.}

4. _{Найдите способ сопоставления N-ых степеней, где N - некоторая постоянная> = 2. Например, сопоставьте идеальные квадраты. (Для разминки, сопоставьте главные силы .)}

5. _{Подходим правильные операторы умножения. Подходим треугольные числа.}

6. _{Сопоставьте числа Фибоначчи (если вы такой же сумасшедший, как и я), или если вы хотите придерживаться чего-то более короткого, сопоставьте правильные утверждения возведения в степень (для разминки верните в качестве совпадения логарифм в основании 2 степени 2) бонус, сделайте то же самое для любого числа, округляя его, как вам нравится), или факториальные числа (для разминки, сопоставьте примитивные числа ).}

7. _{Подберите обильные цифры (если вы такой же сумасшедший, как и я)}

8. _{Вычислите иррациональное число с требуемой точностью (например, разделите входные данные на квадратный корень из 2, возвращая округленный результат как совпадение)}

_{( Движок регулярных выражений, который я написал, может быть полезен, так как он очень быстр в унарных математических регулярных выражениях и включает унарный числовой режим, который может проверять диапазоны натуральных чисел (но также имеет строковый режим, который может оценивать неунарные регулярные выражения, или унарный с разделителями.) По умолчанию он совместим с ECMAScript, но имеет необязательные расширения (которые могут выборочно добавлять подмножества PCRE, или даже молекулярную перспективу, то, чего нет у других движков регулярных выражений).)}

В противном случае, читайте дальше, а также читайте эту GitHub Gist (предупреждение, много спойлеров), в которой рассказывается о том, как подтолкнуть регулярное выражение ECMAScript для решения функций с натуральными числами возрастающей сложности (начиная с набора головоломок teukon, не все из которых математические, что вызвало это поездка).

Как и в других решениях регулярных выражений для этой задачи, входные данные задаются в виде двух чисел в биективном унарном виде, разделенных запятой, представляющей инклюзивный диапазон. Только один номер возвращается. Регулярное выражение можно изменить так, чтобы оно возвращало все числа, которые имеют одинаковый наименьший по величине простой фактор, в виде отдельных совпадений, но для этого требовалось бы смотреть назад с переменной длиной и либо заглядывать вперед, либо \Kвозвращать результат в виде захвата вместо совпадения.

Используемая здесь техника повторного неявного деления на наименьший простой множитель идентична той, которая используется в строках Match, длина которых является четвертым степенным ответом, который я опубликовал некоторое время назад.

Без дальнейших церемоний: ((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$

Вы можете попробовать это здесь.

И свободная версия, с комментариями:

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

Алгоритм можно легко перенести в ECMAScript, заменив вызов подпрограммы копией подпрограммы и вернув совпадение в качестве группы захвата вместо использования \ K. Результат длиной 80 байт:

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

Попробуйте онлайн!

Обратите внимание, что ((.+).*)это можно изменить ((.+)+), уменьшив размер на 1 байт (от 66 до 65 байт ) без потери правильной функциональности, но регулярное выражение экспоненциально взрывается в медленности.

Попробуйте онлайн! _{^{(79-байтовая версия ECMAScript с экспоненциальным замедлением)}}

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

Находит плавность чисел путем пробного деления до тех пор, пока число не станет 1. iсохраняет наименьшую гладкость, jхранит число, которое дало эту гладкость.

Спасибо @xnor за игру в гольф.

J, 22 20 19 символов

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

Например

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

(Функции, принимающие два аргумента, являются инфиксными в J.)

Haskell, 96 94 93 86 80 символов

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]

использование через GHCi (оболочка Haskell):

>5 # 9
8
>9 # 15
9

РЕДАКТИРОВАТЬ: теперь гораздо более простой алгоритм.

это решение включает оба числа в диапазоне (так 8 # 9и 7 # 8есть 8)

объяснение:

Функция (%) принимает два параметра, x и y. когда у равен 2, функция возвращает гладкость х.

Алгоритм отсюда прост - получить объединенный список всех гладкостей чисел на входе с каждой гладкостью, хранящей ссылку на его исходное число, затем отсортировать, чтобы получить наименьшее, и вернуть его ссылочное число.

Вот версия javascript без гольфа с тем же алгоритмом:

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 символов

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

Очень простая реализация спецификации как безымянной функции.

• Получи ассортимент (включительно).
• Фактор всех целых чисел.
• Найти минимум, отсортированный по наибольшему простому коэффициенту.

Луа - 166 символов

У меня не было (пока!) Достаточно репутации, чтобы комментировать решение AndoDaan , но вот некоторые улучшения в его коде

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)

Изменения:

• n%d==0С помощью n%d<1которого эквивалентна в этом случае
• Убрал пробел
• Заменяется table.insert(f,d)на f[#f+1]=d ( #fэто количество элементов f)

Bash + coreutils, 56 байт

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

Входные данные поступают только из двух аргументов командной строки (спасибо @ nyuszika7h !!!). Вывод - единственный результат, напечатанный в STDOUT.

• seq предоставляет диапазон чисел, по одному на строку, из аргументов командной строки.
• factorчитает эти числа и выводит каждое число, за которым следует двоеточие и отсортированный список простых факторов этого числа. Таким образом, самый большой главный фактор находится в конце каждой строки.
• Первый sedудаляет двоеточие и все, кроме последнего / наибольшего простого множителя, поэтому оставляет список каждого числа (столбец 1) и его наибольшего простого множителя (столбец 2).
• sort численно в порядке возрастания по столбцу 2.
• Финал sedсоответствует строке 1 (число, у которого наибольший простой множитель является наименьшим в списке), удаляет все, включая и после первого пробела, затем выходит. sedавтоматически печатает результат этой замены перед выходом.

Выход:

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

Диапазоны Примечание В этом контексте с учетом обеих конечных точек.

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)

Размышления о другом гольфе дали мне идею нового алгоритма проверки гладкости, отсюда и поздний ответ.

Первичная факторизация факториала i!включает в себя не более чем простые числа i. Таким образом, если nэто произведение различных простых чисел, его гладкость (наибольший простой множитель) является наименьшим, iдля которого nделителем является i!. Чтобы учесть повторяющиеся простые факторы в n, мы можем вместо этого использовать достаточно высокую степень i!. В частности, (i!)**nхватает.

Код пытается увеличить факториалы F=i!, обновляется рекурсивно. Мы фильтруем делители Fво входном диапазоне и выводим их, если они есть, и в противном случае переходим к (i+1)!.

Прецедент:

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

С,  149   95

Отредактированный ответ:

Я не могу претендовать на кредит за это решение. Этот обновленный ответ заимствует прекрасный метод, используемый isaacg в своем решении Python. Я хотел бы видеть , если это было возможно , чтобы записать его в C в виде вложенной for/ whileпетли с не фигурными скобками, и это!

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

Объяснение:

• Функция R(a,b,n,q,p,m)сканирует диапазон aдо b-1и возвращает первый найденный номер гладкий. Вызов требует соблюдения следующего вида: R(a,b,a,b,2,0)так что переменные внутри функции эффективно инициализируется следующим образом : n=a;q=b;p=2;m=0;.

Оригинальный ответ :

Это был мой оригинальный ответ ...

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

Объяснение:

• Функция P(n,f,p)проверяет значение nна простоту и возвращает истину (ненулевое), если nпростое, или ложь (ноль), если nне простое. fи pоба должны быть переданы как 1.
• Функция G(n,f)возвращает наибольший простой множитель n. fдолжен быть передан как n.
• Функция R(a,b,p,n)сканирует диапазон aдо b-1и возвращает первый найденный номер гладкий. pдолжен быть передан как 1. nможет быть любым значением.

Тестовый водитель:

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

Выход:

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)

Пример использования:

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

Q, 91 символов K, 78 символов

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

К, вероятно, побрил бы дюжину символов

редактировать: действительно, рассматривая верхнюю границу как не включающую на этот раз

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

Примечание: этот ответ недопустим.

Этот ответ использует несколько функций Pyth, добавленных после того, как задан вопрос.

Я добавил еще одну новую функцию - вызов унарного диапазона в кортеже из 2 элементов, который сокращает решение на два символа:

Пиф , 7

hoePNUQ

Ввод теперь взят через запятую. В остальном то же самое.

В этом ответе используется особенность Pyth, которая была добавлена ​​после того, как был задан этот вопрос, особенно после просмотра замечательного решения CJam от @ aditsu. При этом я хотел продемонстрировать, что добавление этой функции сделало возможным. Эта функция - функция Parity-1, которая при целочисленном вводе возвращает список всех основных факторов ввода, отсортированных от наименьшего к наибольшему.

Пиф , 9

hoePNrQvw

Использует диапазоны в стиле Python, разделенные новой строкой на STDIN. Выводит наименьшее решение для STDOUT.

Объяснение:

      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.

тесты:

$ 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 символов

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)

Я действительно должен прекратить играть в гольф в Луа. Нет никакого смысла.

Clojure - 173 170 символов

Я новичок в Clojure. Golfed:

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

Образцы прогонов:

Диапазоны включают нижний предел, исключая верхний: [a, b) печатает только одно из самых гладких чисел, если встречается несколько.

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

выходы:

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

Руби, 65 62

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

С извинениями за https://codegolf.stackexchange.com/a/36484/6828 , это версия игры в гольф (и немного упрощенная). Использует инклюзивный диапазон, так как он короче.

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 

И спасибо YenTheFirst за сохранение трех символов.

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

Он берет начало и длину из командной строки и возвращает наибольшее гладкое число.

Я использовал ответы здесь и здесь, чтобы сделать свой ответ.

Спасибо VisualMelon за то, что он настроил его и сбрил 12 байтов! Я также избавился от скобок в сохраняющих 2 байта, и CodeInChaos указал на некоторые очевидные вещи, которые я пропустил (спасибо еще раз).

Р, 83

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

где нижняя часть входного диапазона назначена, aа верхняя (включительно) назначена b.

gmpэто пакет, который доступен на CRAN. Это было грязно, пока я не увидел эту абсурдную mfфункцию в CJam. Установите, набрав install.packages("gmp")в консоли.

PowerShell - 85

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

Это позволит отсортировать диапазон чисел (включительно) на основе максимального простого множителя каждого числа. Возвращает самый низкий отсортированный элемент.

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

J - 16 символов

Использование стиля диапазона ( начало , длина ), как разрешено в комментариях.

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

Для использования в качестве двоичного глагола: левый аргумент - начало , правый - длина .

   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

Решение ( начало , конец ) составляет +2 символа и исключает конец; включая конец +2 больше. Но с другой стороны, это выглядит довольно красиво, поскольку мы сопоставляем все {фигурные скобки}.

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

Серьезно, 8 * 14/7 = 16 (неконкурентный)

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

Серьезно был создан после этого конкурса, но я хотел опубликовать этот ответ, потому что он иллюстрирует тип задач, в которых Серьезно хорош.

Попробуйте онлайн!

Объяснение:

,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 байт

.mePbrF

Попробуй это здесь!

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

Кобра - 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

Даже не уверен, почему я беспокоился, Кобра просто не может конкурировать здесь.

Рубин - 113 символов

Использование stdlib. Возвращает один результат. Проверено на 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

(разрыв строки может быть удален). Принимает две конечные точки инклюзивного диапазона на двух строках стандартного ввода (потому что <>это дешевле, чем доступ ARGV) и выводит самый плавный вывод на стандартный вывод. Если есть галстук для самых гладких, печатает самые маленькие. Могли печатать самые большие по стоимости одного персонажа.

Алгоритм - это, по сути, способ Исаака найти самый главный фактор, хотя мы и придумали его независимо. Эта часть великолепно сводится к одному утверждению в perl, а остальная часть требует больше времени, чем хотелось бы.

Должно быть использовано под преамбулой perl -Eили с use 5.012преамбулой. Если вы не можете этого сделать, замените say$rна 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)

Решение @ isaacg , но с minпомощью функциональной клавиши вместо явного поиска мин и рекурсивной функции, выполняющей роль итерации.

Запустите в Stackless Python, чтобы избежать ограничений рекурсии.

Выглядит расточительно, используя условие парантезирования (n%p<1), затем повторяя его отрицание также и в парантезах (n%p>0), но это было лучшее, что я получил. Я пробовал разные вещи, но они оказались хуже.

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

Я приветствую любые улучшения, о которых вы можете подумать.

Java 8 - 422 454 символа

Я изучаю Java 8, и хотел дать этому шанс относительно Java (или даже потоков Java 8).

По сравнению с другими языками это жестокое, но интересное упражнение.

Golfed:

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

пример запуска с использованием:

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

192

MATL ( неконкурентный ), 20 байтов

Этот язык был разработан после испытания

Диапазон включительно на обоих концах. Числа взяты как два отдельных входа.

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

Попробуйте онлайн!

объяснение

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

Желе , 7 байт, оценка = 7 ÷ 7 × 8 = 8, вызов языковых постдатантов

rÆfṀ$ÐṂ

Попробуйте онлайн!

Принимает нижнюю и верхнюю конечные точки диапазона как два отдельных аргумента. Выводит список всех самых гладких чисел в диапазоне. (Это можно рассматривать как функцию, в этом случае выходные данные представляют собой список Jelly, или как полную программу, и в этом случае выходные данные используют то же представление списка, что и JSON.)

объяснение

Те времена, когда ваша программа Jelly - это буквальный перевод спецификации…

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