Оставь все квадраты, вы, которые разделяют меня

37

Определения

  • Идеальный квадрат представляет собой целое число , которое может быть выражено как квадрат другого целого числа. Например, 36это идеальный квадрат, потому что 6^2 = 36.
  • Бесквадратное число является целым числом , которое не делится на любой совершенной площади, за исключением 1. Например, 10это число без квадратов. Тем 12не менее, это не квадратное число, потому что 12делится на 4и 4является идеальным квадратом.

задача

Учитывая положительное целое число n, выведите наибольшее число без квадратов, которое делится n.

Testcases

n   output
1   1
2   2
3   3
4   2
5   5
6   6
7   7
8   2
9   3
10  10
11  11
12  6
13  13
14  14
15  15
16  2
17  17
18  6
19  19
20  10
21  21
22  22
23  23
24  6
25  5
26  26
27  3
28  14
29  29
30  30
31  31
32  2
33  33
34  34
35  35
36  6
37  37
38  38
39  39
40  10
41  41
42  42
43  43
44  22
45  15
46  46
47  47
48  6
49  7
50  10

счет

Это . Кратчайший ответ в байтах побеждает.

Применяются стандартные лазейки .

Ссылка

Дрянная Монахиня
источник
1
... и называется радикальным - так 1980-х годов!
Джонатан Аллан
Тесно связаны , просто умножьте два выхода. Изменить: не берите в голову, это соответствует только на кубических числах.
xnor

Ответы:

45

05AB1E , 2 байта

fP

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

Как это работает

f   Implicitly take input and compute the integer's unique prime factors.
 P  Take the product.
Деннис
источник
26
> _> действительно ... ??
HyperNeutrino
@HyperNeutrino да - если число не является квадратом, это потому, что некоторые из его основных факторов имеют кратность.
Джонатан Аллан
@JonathanAllan Я просто интересуюсь встроенным для уникальных простых факторов. Хотел бы я, чтобы у Желе был один из них ...
HyperNeutrino
@HyperNeutrino Это 05AB1E, привыкнуть к этому. 05AB1E имеет несколько действительно избыточных встроенных функций, которые, очевидно, экономят байты.
Эрик Outgolfer
6
Исправление, "сохранить байты", нет, вероятно, об этом.
Draco18s
14

Брахилог , 3 байта

ḋd×

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

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

объяснение

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply
Fatalize
источник
1
Опять же, Brachylog побеждает Jelly, потому что двухбайтовый атом здесь только один байт. > :-P
HyperNeutrino
4
Желе с большим количеством встроенных компонентов часто рассматривается как преимущество; но больше встроенных средств означает, что им в среднем нужны более длинные имена. Таким образом, есть компромиссы, связанные с дизайном языка игры в гольф.
2
Я не пытаюсь быть «тем парнем», и, может быть, я просто неправильно понимаю подсчет байтов, но разве это не 6 байтов? mothereff.in/byte-counter#ḋd ×
Капитан Мэн
5
@CaptainMan Brachylog использует пользовательскую кодовую страницу на 256 символов, которую вы можете найти здесь .
фатализировать
14

JavaScript (ES6), 55 54 50 46 байт

Цитируя OEIS :
a (n) - наименьший делитель u из n такой, что n делит u ^ n

Обновленная реализация:
a (n) - наименьший делитель u из n натуральных чисел u, такой что n делит u ^ n

let f =

n=>(g=(p,i=n)=>i--?g(p*p%n,i):p?g(++u):u)(u=1)

for(n = 1; n <= 50; n++) {
  console.log(n,f(n));
}

Arnauld
источник
Хороший подход к проблеме, особенно учитывая отсутствие встроенной факторизации
Riking
12

MATL , 6 4 байта

2 байта сохранены с помощью @LeakyNun

Yfup

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

объяснение

Рассмотрим ввод 48.

Yf   % Implicit input. Push prime factors with repetitions.  STACK: [2 2 2 2 3]
u    % Unique.                                               STACK: [2 3]
p    % Product of array. Implicit display.                   STACK: 6
Луис Мендо
источник
@LeakyNun Хех, я собирался опубликовать это :-) Спасибо
Луис Мендо
9

CJam , 8 байт

rimf_&:*

Почему каждая операция в этой программе должна быть 2 байта -_-

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

ri       e# Read int from input
  mf     e# Get the prime factors
    _&   e# Deduplicate
      :* e# Take the product of the list
Бизнес Кот
источник
Я не мог найти способ дедупликации. Ницца!
Луис Мендо
@ LuisMendo Я только что обнаружил это недавно. Я всегда думал, что это пересечение с множеством множеств, но, видимо, это просто нормальное пересечение множеств.
Business Cat
9

Сетчатка , 36 30 28 байт

+`((^|\3)(^(1+?)|\3\4))+$
$3

Ввод и вывод в одинарный .

Попробуйте онлайн! (Включает верхний и нижний колонтитулы для десятичного <-> унарного преобразования и для запуска нескольких тестовых случаев одновременно.)

объяснение

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

(^1|11\1)+$

Так как мы не хотим сопоставлять идеальные квадраты, а числа, которые делятся на квадрат, мы заменяем 1это самой обратной ссылкой:

(^(1+?)|\1\2\2)+$

Таким образом, теперь внешняя группа 1будет использоваться n раз, где n 2 - это самый большой квадрат, который делит входные данные, а группа 2хранит оставшийся коэффициент. Нам нужно разделить целое число на n, чтобы убрать квадрат. Результат может быть выражен как число итераций группы 1времен группы 2, но это немного сложно сделать. Retina - х $*, вероятно , скоро будет улучшено , чтобы взять несимвольный маркер в его правый аргументе в этом случае мы могли бы просто заменить это $#1$*$2, но пока не работает.

Вместо этого мы разлагаем нечетные числа по-разному. Давайте вернемся к более простому примеру соответствия идеальных квадратов с (^1|11\1)+$. Вместо счетчика, \1который инициализируется в 1 и увеличивается на 2 на каждой итерации, у нас будет два счетчика. Один инициализируется до 0, а другой инициализируется до 1 , и они оба увеличиваются на 1 на каждой итерации. Таким образом, мы в основном разложили нечетные числа 2n + 1 в (n) + (n + 1) . Преимущество заключается в том , что мы в конечном итоге с п в одной из групп. В простейшем виде это выглядит так:

((^|1\2)(^1|1\3))+$

Там , где \2это п и \3является п + 1 . Однако мы можем сделать это немного более эффективно, заметив, что n + 1 одной итерации равно n следующей итерации, поэтому мы можем сэкономить на 1здесь:

((^|\3)(^1|1\3))+$

Теперь нам просто нужно вернуться к использованию начального коэффициента вместо того, 1чтобы сопоставлять входные данные, которые делятся на идеальный квадрат:

((^|\3)(^(1+?)|\3\4))+$

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

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

Мартин Эндер
источник
8

Октава, 27 байт

@(x)prod(unique(factor(x)))

Подобный подход, как и другие ответы. Разница в том, что функции имеют гораздо более длинные имена. Я считаю, что код действительно объясняет себя: принимает prodчисло uniqueпростых factorчисел числа.

Стьюи Гриффин
источник
Вы ниндзя меня на ~ 30 секунд :)
Kritixi Lithos
7

Wolfram Language, 29 28 байт

-1 Спасибо @Martin Ender ♦

Most[1##&@@FactorInteger@#]&

Объяснение:

           FactorInteger@#    (*Get prime factorization as {{a,b},{c,d}}*)
     1##&@@                   (*Multiply list elements together, to get the product of the factors and the product of their exponents*)
Most[                     ]&  (*Take the first element*)
Скотт Милнер
источник
2
Просто понял, что это в основном комментарий @ GregMartin к ответу Mathics, только меньше в гольфе ...
Скотт Милнер
Не расстраивайся, у меня был еще менее гольфистский ответTimes@@(#&@@@FactorInteger@#)&
Ian Miller
Mostоставляет это как список. Вам нужно Firstполучить значение.
Ян Миллер
@IanMiller Я понимаю, что это меньше байтов, чтобы просто вернуть список только с одним элементом. Я предположил, что это было хорошо, так как это все еще разумный вывод.
Скотт Милнер,
7

Python , 37 байт

f=lambda n,r=1:1>>r**n%n or-~f(n,r+1)

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

Наибольший квадратный делитель n- это наименьшее число rсо всеми первыми nфакторами. Мы можем проверить это как r**n%n==0, поскольку r**nсоздаем nкопии каждого простого множителя r, и делится на него, nтолько если представлен каждый из nосновных факторов.

Это 1>>r**n%nэквивалентно int(r**n%n==0). Если Trueможно использовать вывод 1, это на 2 байта короче.

f=lambda n,r=1:r**n%n<1or-~f(n,r+1)
XNOR
источник
6

Математика , 40 байт

Times@@(Transpose@FactorInteger@#)[[1]]&

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

Павел
источник
Times@@#&@@Transpose@FactorInteger@#&сохраняет 3 байта ( #&@@это стандартная уловка, [[1]]и в подобных случаях часто можно сохранить дополнительные байты в скобках).
Мартин Эндер
Вы также можете использовать Threadвместо Transpose. В Mathematica также есть 3-байтовый оператор для Transpose, но я не знаю, поддерживает ли Mathics его.
Мартин Эндер
6
#&@@(1##&@@FactorInteger@#)&избегает необходимости в Transposeцелом. ( 1##&@@Только Times@@в маскировке, которая прекрасно работает на упорядоченных пары , обеспечиваемых FactorInteger, и '#&@@это First@в маскировке.)
Грег Мартин
@GregMartin это в основном ваше собственное решение, не стесняйтесь размещать его, если хотите.
Павел
Похоже, Скотт Милнер все равно получил это :)
Грег Мартин
5

Алиса , 4 байта

iDo@

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

Ввод и вывод даны как кодовая точка символа (работает для всех допустимых кодовых точек Unicode).

объяснение

Что ж, у Алисы есть встроенная Dфункция, чье определение «Дедуплицированные простые факторы». То есть, пока значение делится на некоторое p 2 для простого p , делим это значение на p . Это как раз та функция, которая требуется для этой задачи. Остальное только ввод, вывод, завершение программы.

Причина, по которой это было добавлено к Алисе, на самом деле не имеет ничего общего с этой целочисленной последовательностью. Я пытался придерживаться темы ассоциирования делителей с подстроками и простых факторов с символами. И мне нужна была функция, которая работает с «дедуплицирующими символами» (которая в целом гораздо полезнее, потому что она позволяет вам рассматривать строки как наборы, особенно когда они используются вместе с различными операторами мультимножества).

Мартин Эндер
источник
Грустная часть, даже со встроенным, это не самый короткий ответ.
Rɪᴋᴇʀ
@Riker Ну, это потому, что Алиса не является языком игры в гольф, поэтому она требует явного ввода-вывода и (так как это 2D-язык) завершения программы.
Мартин Эндер
Да, все еще немного грустно, хотя.
Rɪᴋᴇʀ
@ ConorO'Brien Мы только что обсуждали это в другом месте, и это верно только в том случае, если автономный оператор является выражением, которое вычисляет функцию (здесь это не так, поскольку функции / операторы не являются первоклассными значениями) , codegolf.meta.stackexchange.com/a/7206/8478
Мартин Эндер
@ ConorO'Brien извините, это было эксклюзивное "мы".
Мартин Эндер
1

Pyth, 8 6 байтов

*F+1{P

* -2 байта благодаря @LeakyNun

Было бы 3, если бы Pyth имел встроенный для продуктов списков ...

Попытайся!

*F+1{P
      Q     # Implicit input
     P      # Prime factors of the input
    {       # Deduplicate
  +1        # Prepend 1 to the list (for the case Q==1)
*F          # Fold * over the list
KarlKastor
источник
Вы можете использовать *F+1{Pвместо этого.
Утренняя монахиня
1

C 65 50 байт

Спасибо @ Örjan Johansen за устранение необходимости r. Благодаря этому и другим грязным трюкам мне удалось выжать 15 байтов!

d;f(n){for(d=1;d++<n;)n%(d*d)||(n/=d--);return n;}

whileушел и заменил на ||указатель поворота. <=должен был быть <все время.

<=поворачивается <на приращение, чтобы получить n%(++d*d)(должно быть четко определено из-за приоритета оператора).


Оригинальный код:

d;r;f(n){for(r=d=1;d++<=n;)while(n%d<1)r*=r%d?d:1,n/=d;return r;}
algmyr
источник
Я думаю, что вы можете сократить его, удалив rи вместо этого использовать while(n%(d*d)<1)n/=d;.
Орджан Йохансен,
@ ØrjanJohansen Это кажется правильным. Я думал о строительстве, а не о сокращении. У меня есть некоторые дополнительные улучшения, которые будут добавлены в ближайшее время.
Альгмир
++d*dабсолютно не определяется стандартами Си - это классический случай явно неопределенного поведения. Но мы все равно будем здесь реализовывать.
Орджан Йохансен,
На самом деле, не должно d++<n, что хорошо определено, все еще работать? Я думаю, что старая версия прошла весь путь n+1(безвредно).
Орджан Йохансен,
Вы, вероятно, правы по поводу неопределенного поведения. По некоторым причинам я думал, что приоритет оператора решит это. В большинстве примеров UB, которые я видел, используются операторы с одинаковыми приоритетами, но, конечно, здесь также есть гонка данных. Вы также правы в том, d++<nчто вы правы, по какой-то причине я не видел этого, когда переписывал код.
algmyr
0

Аксиома, 89 байт

f(x:PI):PI==(x=1=>1;g:=factor x;reduce(*,[nthFactor(g,i) for i in 1..numberOfFactors g]))

тест и результаты

(38) -> [[i, f(i)] for i in 1..30 ]
   (38)
   [[1,1], [2,2], [3,3], [4,2], [5,5], [6,6], [7,7], [8,2], [9,3], [10,10],
    [11,11], [12,6], [13,13], [14,14], [15,15], [16,2], [17,17], [18,6],
    [19,19], [20,10], [21,21], [22,22], [23,23], [24,6], [25,5], [26,26],
    [27,3], [28,14], [29,29], [30,30]]

это одна из неиспользуемых функций factor ()

g(x:PI):PI==(w:=sqrt(x);r:=i:=1;repeat(i:=i+1;i>w or x<2=>break;x rem i=0=>(r:=r*i;repeat(x rem i=0=>(x:=x quo i);break)));r)

но это всего 125 байтов

RosLuP
источник
0

R, 52 байта

`if`((n=scan())<2,1,prod(unique(c(1,gmp::factorize(n))))

читает nсо стандартного ввода. Требует установки gmpбиблиотеки (чтобы TIO не работал). Использует тот же подход, что и многие из приведенных выше ответов, но он падает на входе 1, потому что factorize(1)возвращает пустой вектор класса bigz, который unique, увы , падает .

Giuseppe
источник
Это выводит 12, когда я
Flounderer
@Flounderer вы правы, я обновил код.
Джузеппе
0

Пыть , 3 байта

←ϼΠ

Объяснение:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print
mudkip201
источник