Definicje
- Kwadratem jest liczbą całkowitą, która może być wyrażona jako kwadrat innej liczby całkowitej. Na przykład
36
jest 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ład10
jest liczbą bez kwadratów. Nie12
jest to jednak liczba bez kwadratów, ponieważ12
jest podzielna przez4
i4
jest 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 golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa.
Odniesienie
code-golf
math
arithmetic
number-theory
Leaky Nun
źródło
źródło
Odpowiedzi:
05AB1E , 2 bajty
Wypróbuj online!
Jak to działa
źródło
Brachylog , 3 bajty
Wypróbuj online!
Bardzo oryginalna odpowiedź ...
Wyjaśnienie
źródło
JavaScript (ES6),
55545046 bajtówCytując OEIS :
a (n) jest najmniejszym dzielnikiem u takim, że n dzieli u ^ n
Zaktualizowana implementacja:
a (n) to najmniejszy
dzielnik udodatniej liczby całkowitej u taki, że n dzieli u ^ nźródło
MATL ,
64 bajtów2 bajty zapisane przy pomocy @LeakyNun
Wypróbuj online!
Wyjaśnienie
Rozważ wejście
48
.źródło
Galaretka , 4 bajty
Wypróbuj online!
źródło
CJam , 8 bajtów
Dlaczego każda operacja w tym programie musi mieć 2 bajty -_-
Wypróbuj online!
źródło
Retina ,
363028 bajtówWejś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:
Ponieważ nie chcemy dopasowywać idealnych kwadratów, ale liczby, które można podzielić przez kwadrat, zastępujemy
1
to samym odwołaniem wstecznym:Zatem teraz grupa zewnętrzna
1
będzie używana n razy, gdzie n 2 jest największym kwadratem dzielącym dane wejściowe, a grupa2
przechowuje pozostały czynnik. Chcemy podzielić liczbę całkowitą przez n, aby usunąć kwadrat. Wynik można wyrazić jako liczbę iteracji grupy1
razy grupa2
, 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,\1
któ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:Gdzie
\2
jest n i\3
jest 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ć na1
tutaj:Teraz musimy wrócić do używania współczynnika początkowego zamiast
1
dopasowywania danych wejściowych podzielonych przez idealny kwadrat:Teraz wszystko, co musimy zrobić, to zastąpić to wszystko
$3
na 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.źródło
Oktawa, 27 bajtów
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
prod
UCT zunique
pierwszychfactor
s liczby.źródło
Wolfram Language,
2928 bajtów-1 Dzięki @Martin Ender ♦
Wyjaśnienie:
źródło
Times@@(#&@@@FactorInteger@#)&
Most
pozostawia to jako listę. MusiszFirst
uzyskać wartość.Python , 37 bajtów
Wypróbuj online!
Największym dzielnikiem bez kwadratów
n
jest ta najmniejsza liczbar
ze wszystkimin
pierwszymi czynnikami. Możemy to sprawdzićr**n%n==0
, ponieważ, ponieważr**n
wykonujemyn
kopie każdego czynnika pierwszegor
, i można je podzielićn
tylko wtedy, gdy każdy zn
czynników pierwszych jest reprezentowany.Jest
1>>r**n%n
to równoważne zint(r**n%n==0)
. JeśliTrue
można użyć wyjścia 1, jest to 2 bajty krótsze do zrobienia.źródło
Matematyka , 40 bajtów
Wypróbuj online!
ź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).Thread
zamiastTranspose
. W Mathematica jest też 3-bajtowy operatorTranspose
, ale nie wiem, czy Mathics go obsługuje.#&@@(1##&@@FactorInteger@#)&
unika potrzebyTranspose
całkowicie. (1##&@@
jest tylkoTimes@@
w przebraniu, co świetnie działa na uporządkowanych parach uzyskanych przezFactorInteger
; i'#&@@
jestFirst@
w przebraniu).Alice , 4 bajty
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ą
D
definicję, 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).
źródło
Haskell , 31 bajtów
Wypróbuj online!
źródło
Pyke , 3 bajty
Wypróbuj online!
źródło
Prolog (SWI) ,
8439 bajtówWypróbuj online!
Dostosowano pomysł odpowiedzi Haskella @ xnora na Prolog.
źródło
PHP, 70 bajtów
Wypróbuj online!
źródło
Pyth,
86 bajtów* -2 bajty dzięki @LeakyNun
Byłoby 3, gdyby Pyth miał wbudowane produkty list ...
Spróbuj!
źródło
*F+1{P
.C,
6550 bajtówDzięki @ Ørjan Johansen za usunięcie potrzeby
r
. Dzięki temu i kilku innym brudnym sztuczkom udało mi się wycisnąć 15 bajtów!while
zniknął i został zastąpiony przez||
i indeksowanie.<=
powinien był być<
cały czas.<=
zwrócony<
przez przesunięcie przyrostka do uzyskanian%(++d*d)
(powinien być dobrze zdefiniowany ze względu na pierwszeństwo operatora).Oryginalny kod:
źródło
r
i zamiast tego używaćwhile(n%(d*d)<1)n/=d;
.++d*d
absolutnie nie jest dobrze zdefiniowany przez standardy C. - jest to klasyczny przypadek wyraźnie nieokreślonego zachowania. Ale i tak przechodzimy tutaj przez implementacje.d++<n
, co jest dobrze zdefiniowane, nadal działać? Myślę, że stara wersja poszła na całośćn+1
(nieszkodliwie).d++<n
poprawność, z jakiegoś powodu nie widziałem tego, kiedy przepisałem kod.Aksjomat, 89 bajtów
test i wyniki
jest to jedyna nieużywana funkcja factor ()
ale to tylko 125 bajtów
źródło
R, 52 bajty
czyta
n
ze standardowego. Wymaga zainstalowaniagmp
biblioteki (aby TIO nie działało). Stosuje to samo podejście, co wiele z powyższych odpowiedzi, ale ulega awarii na wejściu1
, ponieważfactorize(1)
zwraca pusty wektor klasybigz
, który ulega awariiunique
, niestety.źródło
Właściwie 2 bajty
Wypróbuj online!
Wyjaśnienie:
źródło
Pari / GP , 28 bajtów
Wypróbuj online!
źródło
Pyt , 3 bajty
Wyjaśnienie:
źródło