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 golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa.

Obowiązują standardowe luki .

Odniesienie

• OEIS A007947

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.

Brachylog , 3 bajty

ḋd×

Wypróbuj online!

Bardzo oryginalna odpowiedź ...

Wyjaśnienie

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply

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

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

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

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

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

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.

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

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)

Matematyka , 40 bajtów

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

Wypróbuj online!

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

Haskell , 31 bajtów

f n=until(\r->r^n`mod`n<1)(+1)1

Wypróbuj online!

Pyke , 3 bajty

P}B

Wypróbuj online!

P   -   factors(input)
 }  -  uniquify(^)
  B - product(^)

Prolog (SWI) , 84 39 bajtów

f(N,P):-between(1,N,P),P^N mod N=:=0,!.

Wypróbuj online!

Dostosowano pomysł odpowiedzi Haskella @ xnora na Prolog.

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!

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

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

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

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.

Właściwie 2 bajty

yπ

Wypróbuj online!

Wyjaśnienie:

yπ
y   prime divisors
 π  product

Pari / GP , 28 bajtów

n->factorback(factor(n)[,1])

Wypróbuj online!

Pyt , 3 bajty

←ϼΠ

Wyjaśnienie:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print