Porzućcie wszystkie kwadraty, wy, którzy mnie dzielicie

37

Definicje

  • Kwadratem jest liczbą całkowitą, która może być wyrażona jako kwadrat innej liczby całkowitej. Na przykład 36jest idealnym kwadratem, ponieważ 6^2 = 36.
  • Liczba bez kwadratów jest liczbą całkowitą, której nie dzieli żaden idealny kwadrat, z wyjątkiem 1. Na przykład 10jest liczbą bez kwadratów. Nie 12jest to jednak liczba bez kwadratów, ponieważ 12jest podzielna przez 4i 4jest kwadratem idealnym.

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą n, wyprowadza największą dzielącą liczbę bez kwadratów n.

Przypadki testowe

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

Punktacja

To jest . Najkrótsza odpowiedź w bajtach wygrywa.

Obowiązują standardowe luki .

Odniesienie

Leaky Nun
źródło
1
... i nazywa się radykałem - więc lata osiemdziesiąte!
Jonathan Allan
Ściśle powiązane , wystarczy pomnożyć dwa wyjścia. Edycja: nieważne, pasuje tylko do liczb nieoznaczonych.
xnor

Odpowiedzi:

45

05AB1E , 2 bajty

fP

Wypróbuj online!

Jak to działa

f   Implicitly take input and compute the integer's unique prime factors.
 P  Take the product.
Dennis
źródło
26
> _> naprawdę ... ??
HyperNeutrino,
@HyperNeutrino tak - jeśli liczba nie jest kwadratem, dzieje się tak dlatego, że niektóre z jej głównych liczb są mnożone.
Jonathan Allan
@JonathanAllan Interesuje mnie tylko wbudowane unikalne czynniki pierwsze. Chciałbym, żeby Jelly miała jeden z nich ...
HyperNeutrino
@HyperNeutrino Jest 05AB1E, przyzwyczaj się do tego. 05AB1E ma kilka naprawdę redundantnych wbudowań, które najwyraźniej oszczędzają bajty.
Erik the Outgolfer
6
Korekta, „zapisz bajty”, prawdopodobnie nie ma o tym mowy.
Draco18s
14

Brachylog , 3 bajty

ḋd×

Wypróbuj online!

Bardzo oryginalna odpowiedź ...

Wyjaśnienie

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply
Fatalizować
źródło
1
Ponownie Brachylog bije Galaretkę, ponieważ dwubajtowy atom ma tylko jeden bajt. > :-P
HyperNeutrino
4
Galaretka posiadająca wiele wbudowanych elementów jest często postrzegana jako zaleta; ale więcej wbudowanych oznacza, że ​​potrzebują one średnio dłuższych nazw. Są więc kompromisy związane z projektowaniem języka golfa.
2
Nie próbuję być „tym facetem” i może po prostu źle rozumiem liczenie bajtów, ale czy to nie 6 bajtów? mothereff.in/byte-counter#ḋd ×
Captain Man
5
@CaptainMan Brachylog używa niestandardowej strony kodowej o 256 znaków, którą można znaleźć tutaj .
Fatalize
14

JavaScript (ES6), 55 54 50 46 bajtów

Cytując OEIS :
a (n) jest najmniejszym dzielnikiem u takim, że n dzieli u ^ n

Zaktualizowana implementacja:
a (n) to najmniejszy dzielnik u dodatniej liczby całkowitej u taki, że n dzieli 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
źródło
Niezłe podejście do problemu, szczególnie. z uwagi na brak wbudowanego faktoryzacji
Riking
12

MATL , 6 4 bajtów

2 bajty zapisane przy pomocy @LeakyNun

Yfup

Wypróbuj online!

Wyjaśnienie

Rozważ wejście 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
Luis Mendo
źródło
Out-golfed
Leaky Nun
@LeakyNun Heh, miałem zamiar to opublikować :-) Dzięki
Luis Mendo
11

Galaretka , 4 bajty

ÆfQP

Wypróbuj online!

ÆfQP  Main link, argument is z
Æf    Takes the prime factors of z
  Q   Returns the unique elements of z
   P  Takes the product
HyperNeutrino
źródło
9

CJam , 8 bajtów

rimf_&:*

Dlaczego każda operacja w tym programie musi mieć 2 bajty -_-

Wypróbuj online!

ri       e# Read int from input
  mf     e# Get the prime factors
    _&   e# Deduplicate
      :* e# Take the product of the list
Business Cat
źródło
Nie mogłem znaleźć sposobu na deduplikację. Miły!
Luis Mendo,
@LuisMendo Właśnie odkryłem to niedawno. Zawsze myślałem, że to skrzyżowanie wielosetowe, ale najwyraźniej to zwykłe ustawione skrzyżowanie.
Business Cat
9

Retina , 36 30 28 bajtów

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

Wejście i wyjście unary .

Wypróbuj online! (Obejmuje nagłówek i stopkę do konwersji dziesiętnej <-> jednoargumentowej i do uruchamiania wielu przypadków testowych jednocześnie.)

Wyjaśnienie

Chodzi o to, aby dopasować dane wejściowe jako kwadrat razy jakiś czynnik. Podstawowe wyrażenie regularne do dopasowania kwadratu wykorzystuje odwołanie do przodu, aby dopasować sumy kolejnych nieparzystych liczb całkowitych:

(^1|11\1)+$

Ponieważ nie chcemy dopasowywać idealnych kwadratów, ale liczby, które można podzielić przez kwadrat, zastępujemy 1to samym odwołaniem wstecznym:

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

Zatem teraz grupa zewnętrzna 1będzie używana n razy, gdzie n 2 jest największym kwadratem dzielącym dane wejściowe, a grupa 2przechowuje pozostały czynnik. Chcemy podzielić liczbę całkowitą przez n, aby usunąć kwadrat. Wynik można wyrazić jako liczbę iteracji grupy 1razy grupa 2, ale jest to nieco trudne. $*Prawdopodobnie wkrótce Retina zostanie ulepszona, aby przyjmować token niebędący postacią jako argument po prawej stronie, w którym to przypadku moglibyśmy po prostu ją zastąpić $#1$*$2, ale to jeszcze nie działa.

Zamiast tego różnie rozkładamy liczby nieparzyste. Wróćmy do prostszego przykładu dopasowania idealnych kwadratów (^1|11\1)+$. Zamiast licznika, \1który jest inicjowany na 1 i zwiększany o 2 przy każdej iteracji, będziemy mieli dwa liczniki. Jeden jest inicjowany na 0, a drugi na 1 , i oba są zwiększane o 1 podczas każdej iteracji. Więc w zasadzie dokonaliśmy dekompozycji liczb nieparzystych 2n + 1 na (n) + (n + 1) . Korzyścią jest to, że skończymy z nw jednej z grup. W najprostszej formie wygląda to tak:

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

Gdzie \2jest n i \3jest n + 1 . Możemy to jednak zrobić nieco bardziej efektywnie, zauważając, że n + 1 jednej iteracji jest równa n następnej iteracji, dzięki czemu możemy zaoszczędzić na 1tutaj:

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

Teraz musimy wrócić do używania współczynnika początkowego zamiast 1dopasowywania danych wejściowych podzielonych przez idealny kwadrat:

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

Teraz wszystko, co musimy zrobić, to zastąpić to wszystko $3na końcu, który przechowuje współczynnik początkowy razy liczbę kroków, co usuwa jeden czynnik kwadratu z danych wejściowych.

Odbywa się to wielokrotnie +na samym początku programu, aby uwzględnić dane wejściowe, które zawierają wyższe moce niż kwadraty.

Martin Ender
źródło
8

Oktawa, 27 bajtów

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

Podobne podejście jak inne odpowiedzi. Różnica polega na tym, że funkcje mają znacznie dłuższe nazwy. Wierzę, że kod wyjaśnia się naprawdę: wyraża prodUCT z uniquepierwszych factors liczby.

Stewie Griffin
źródło
Ty ninja'd mnie o ~ 30 sekund :)
Kritixi Lithos
7

Wolfram Language, 29 28 bajtów

-1 Dzięki @Martin Ender ♦

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

Wyjaśnienie:

           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*)
Scott Milner
źródło
2
Właśnie zdałem sobie sprawę, że jest to w zasadzie komentarz GregaMartina do odpowiedzi Mathics, tylko mniej golfa ...
Scott Milner
Nie czuj się źle, miałem jeszcze mniej golfową odpowiedźTimes@@(#&@@@FactorInteger@#)&
Ian Miller
Mostpozostawia to jako listę. Musisz Firstuzyskać wartość.
Ian Miller
@ImMiller Zdaję sobie z tego sprawę, ale mniej bajtów polega na zwróceniu listy z tylko jednym elementem. Założyłem, że to było w porządku, ponieważ wciąż jest to rozsądny wynik.
Scott Milner,
7

Python , 37 bajtów

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

Wypróbuj online!

Największym dzielnikiem bez kwadratów njest ta najmniejsza liczba rze wszystkimi npierwszymi czynnikami. Możemy to sprawdzić r**n%n==0, ponieważ, ponieważ r**nwykonujemy nkopie każdego czynnika pierwszego r, i można je podzielić ntylko wtedy, gdy każdy z nczynników pierwszych jest reprezentowany.

Jest 1>>r**n%nto równoważne z int(r**n%n==0). Jeśli Truemożna użyć wyjścia 1, jest to 2 bajty krótsze do zrobienia.

f=lambda n,r=1:r**n%n<1or-~f(n,r+1)
xnor
źródło
6

Matematyka , 40 bajtów

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

Wypróbuj online!

Pavel
źródło
Times@@#&@@Transpose@FactorInteger@#&oszczędza 3 bajty ( #&@@jest to standardowa sztuczka, [[1]]aw takich przypadkach często zapisuje dodatkowe bajty w nawiasach).
Martin Ender
Możesz także użyć Threadzamiast Transpose. W Mathematica jest też 3-bajtowy operator Transpose, ale nie wiem, czy Mathics go obsługuje.
Martin Ender
6
#&@@(1##&@@FactorInteger@#)&unika potrzeby Transposecałkowicie. ( 1##&@@jest tylko Times@@w przebraniu, co świetnie działa na uporządkowanych parach uzyskanych przez FactorInteger; i '#&@@jest First@w przebraniu).
Greg Martin
@GregMartin to w zasadzie twoje własne rozwiązanie, możesz je opublikować, jeśli chcesz.
Pavel
Wygląda na to, że Scott Milner i tak to otrzymał :)
Greg Martin
5

Alice , 4 bajty

iDo@

Wypróbuj online!

Dane wejściowe i wyjściowe są podawane jako punkt kodowy znaku (działa dla wszystkich prawidłowych punktów kodowych Unicode).

Wyjaśnienie

Cóż, Alice ma wbudowaną Ddefinicję, której definicją jest „Deduplikowane czynniki pierwsze”. To znaczy, o ile wartość jest podzielna przez część p 2 dla liczby pierwszej p , dziel tę wartość przez p . Zdarza się, że jest to dokładnie funkcja wymagana w tym wyzwaniu. Reszta to tylko wejście, wyjście, zakończenie programu.

Powód dodania go do Alicji nie ma nic wspólnego z tą liczbą całkowitą. Próbowałem trzymać się tematu kojarzenia dzielników z podciągami, a czynniki pierwsze z postaciami. Potrzebowałem funkcji, która idzie w parze z „znakami deduplikacji” (co jest ogólnie o wiele bardziej przydatne, ponieważ pozwala traktować ciągi jako zestawy, szczególnie gdy są używane razem z różnymi operatorami wielosetowymi).

Martin Ender
źródło
Smutne jest to, że nawet przy wbudowanym rozwiązaniu nie jest to najkrótsza odpowiedź.
Rɪᴋᴇʀ
@Riker Cóż, to dlatego, że Alice nie jest językiem gry w golfa, dlatego potrzebuje wyraźnego wejścia / wyjścia i (ponieważ jest to język 2D) zakończenia programu.
Martin Ender
Tak, wciąż trochę smutny.
Rɪᴋᴇʀ
@ ConorO'Brien Właśnie przeprowadziliśmy tę dyskusję w innym miejscu i jest to ważne tylko wtedy, gdy samodzielny operator jest wyrażeniem, które ocenia funkcję (co nie ma miejsca w tym przypadku, ponieważ funkcje / operatory nie są pierwszorzędnymi wartościami) . codegolf.meta.stackexchange.com/a/7206/8478
Martin Ender
@ ConorO'Brien przepraszam, że było to wyjątkowe „my”.
Martin Ender
3

Pyke , 3 bajty

P}B

Wypróbuj online!

P   -   factors(input)
 }  -  uniquify(^)
  B - product(^)
niebieski
źródło
2

PHP, 70 bajtów

for($r=1,$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r%$i?$r*=$i:1);echo$r;

Wypróbuj online!

Jörg Hülsermann
źródło
1

Pyth, 8 6 bajtów

*F+1{P

* -2 bajty dzięki @LeakyNun

Byłoby 3, gdyby Pyth miał wbudowane produkty list ...

Spróbuj!

*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
źródło
Zamiast tego możesz użyć *F+1{P.
Leaky Nun
1

C, 65 50 bajtów

Dzięki @ Ørjan Johansen za usunięcie potrzeby r. Dzięki temu i kilku innym brudnym sztuczkom udało mi się wycisnąć 15 bajtów!

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

whilezniknął i został zastąpiony przez ||i indeksowanie. <=powinien był być <cały czas.

<=zwrócony <przez przesunięcie przyrostka do uzyskania n%(++d*d)(powinien być dobrze zdefiniowany ze względu na pierwszeństwo operatora).


Oryginalny kod:

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ódło
Myślę, że można go skrócić, usuwając ri zamiast tego używać while(n%(d*d)<1)n/=d;.
Ørjan Johansen
@ ØrjanJohansen To wydaje się słuszne. Myślałem raczej o budowie niż redukcji. Mam kilka dodatkowych ulepszeń do dodania, wkrótce zaktualizuję.
algmyr
++d*dabsolutnie nie jest dobrze zdefiniowany przez standardy C. - jest to klasyczny przypadek wyraźnie nieokreślonego zachowania. Ale i tak przechodzimy tutaj przez implementacje.
Ørjan Johansen
Właściwie to nie powinno d++<n, co jest dobrze zdefiniowane, nadal działać? Myślę, że stara wersja poszła na całość n+1(nieszkodliwie).
Ørjan Johansen
Prawdopodobnie masz rację co do niezdefiniowanego zachowania. Z jakiegoś powodu myślałem, że pierwszeństwo operatora to rozwiąże. Większość przykładów UB, które widziałem, korzysta z tych samych operatorów priorytetowych, ale oczywiście tutaj również istnieje wyścig danych. Masz również rację, jeśli chodzi o d++<npoprawność, z jakiegoś powodu nie widziałem tego, kiedy przepisałem kod.
algmyr
0

Aksjomat, 89 bajtów

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

test i wyniki

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

jest to jedyna nieużywana funkcja 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)

ale to tylko 125 bajtów

RosLuP
źródło
0

R, 52 bajty

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

czyta nze standardowego. Wymaga zainstalowania gmpbiblioteki (aby TIO nie działało). Stosuje to samo podejście, co wiele z powyższych odpowiedzi, ale ulega awarii na wejściu 1, ponieważ factorize(1)zwraca pusty wektor klasy bigz, który ulega awarii unique, niestety.

Giuseppe
źródło
Daje to wynik 12, gdy wprowadzę 12.
Flądrowiec
@ Założycielu, masz rację, zaktualizowałem kod.
Giuseppe,
0

Pyt , 3 bajty

←ϼΠ

Wyjaśnienie:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print
mudkip201
źródło