Biorąc pod uwagę liczbę n >= 2, wypisz wszystkie dodatnie liczby całkowite mniejsze niż ngdzie gcd(n, k) == 1(przy kczym jest to jedna z liczb wyjściowych). Numery tego rodzaju są względnie pierwsze dla siebie.

Przykład: 10podaje dane wyjściowe [1, 3, 7, 9](w dowolnej formie, pod warunkiem, że liczby są jednoznacznie rozdzielone i znajdują się na liście). Lista nie może zawierać zduplikowanych wpisów i nie musi być sortowana.

Więcej przypadków testowych:

2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]

Nie liczymy również powyższych liczb, nktóre są chronione prawem autorskim n, wyłącznie dlatego, że jestem pewien, że istnieją nieskończone rozwiązania.

Zauważ również: Liczby, które są dla siebie pierwszymi, są również uważane za względnie pierwsze lub wzajemnie pierwsze.

Galaretka , 3 bajty

gÐṂ

Wypróbuj online!

Jak to działa?

gÐṂ - (Monadic) Pełny program.

g - Największy wspólny dzielnik.
 ÐṂ - Zachowaj elementy o minimalnej wartości linku (tj. Te z GCD == 1)
       Zauważ, że automatycznie tworzy to zakres [1, wejście] (włącznie).

Dowód ważności

Ponieważ chcemy wyodrębnić tylko koprime, minimalna wartość listy Greatest-Common-Divisors musi wynosić 1, aby lewka ÐṂdziałała. Udowodnijmy, że (dwiema metodami):

1. Niejawnie wygenerowany zakres zawiera i . Największy wspólny dzielnik jest zawsze ściśle dodatnia, a więc jest gwarantowane miejsce i zawsze będzie wartością minimalną.1 gcd ( 1 , x ) = $[1, \text{input}]$$1$$\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{*}$$1$

2. Dwie kolejne dodatnie liczby całkowite są zawsze chronione prawem autorskim. Rozważ , gdzie . Następnie bierzemy kolejną dodatnią liczbę całkowitą taką jak i . y = x + 1 k k ∣ x k ∣ $x, y \in \mathbb{Z}^{*}$$y = x + 1$$k$$k \mid x$$k \mid y$

   Oznacza to, że , więc , a więc . Jedyną dodatnią liczbą całkowitą do podzielenia jest sama , więc na pewno pojawi się na liście i zawsze będzie wartością minimalną.k ∣ ( x + 1 - x ) k ∣ 1 1 $k \mid (y - x)$$k \mid (x + 1 - x)$$k \mid 1$$1$$1$

Python 2 , 61 47 bajtów

lambda n:[k/n for k in range(n*n)if k/n*k%n==1]

Wypróbuj online!

tło

Rozważmy pierścień . Chociaż ten pierścień jest zwykle definiowany za pomocą klas reszt modulo , można go również traktować jako zbiór , gdzie operatory dodawania i mnożenia są zdefiniowane przez oraz , gdzie oznacza zwykły dodatek, mnożenie i operatory modulo nad liczbami całkowitymi.n Z n = { 0 , … , n - 1 } a + n b = ( a + b $(Z_n, +_n, \cdot_n)$$n$$Z_n = \{0, \dots, n - 1\}$a ⋅ n b = a ⋅ $a +_n b = (a + b)\:\%\: n$+ $a \cdot_n b = a \cdot b\:\%\: n$$+,\:\cdot\text{, and } \%$

Dwa elementy i z nazywane są wzajemne multiplikatywne odwrotności modulo , jeśli . Zauważ, że za każdym razem, gdy .b Z n n a ⋅ n b = $a$$b$$Z_n$$n$$a \cdot_n b = 1\:\%\:n$n > $1\:\%\:n = 1$$n > 1$

Ustalić i pozwolić być względnie pierwsze z w . Jeżeli dwa elementy i w mamy że . Oznacza to, że , a my podążamy za tym , tzn. dzieli równomiernie . Ponieważ nie dzieli pierwszych dzielników z , oznacza to, że . Wreszcie, ponieważa n Z n a ⋅ n x = a ⋅ n y x y Z n a ⋅ $n > 1$$a$$n$$Z_n$$a \cdot_n x = a \cdot_n y$$x$$y$$Z_n$a ⋅ ( x - y $a \cdot x\:\%\:n = a \cdot y\:\%\:n$n ∣ a ⋅ ( x - y ) n a ⋅ ( x - y ) n a n ∣ x - y - n < x - y < n x = y a ⋅ n 0 , … , a ⋅ n ( n - 1 ) Z n Z n n 1 b $a \cdot (x - y)\:\%\:n = a \cdot x\:\%\:n - a \cdot y\:\%\:n = 0$$n \mid a \cdot (x - y)$$n$$a \cdot (x - y)$$n$$a$$n \mid x - y$$-n < x - y < n$ , wnioskujemy, że . To pokazuje, że produkty są różnymi elementami . Od ma dokładnie elementów, jedną (i) dokładnie jeden z tych produktów może być równa , to znaczy, jest unikalny w taki sposób, że .$x = y$$a \cdot_n 0, \dots, a \cdot_n (n - 1)$$Z_n$$Z_n$$n$$1$ $b$ a ⋅ n b = $Z_n$$a \cdot_n b = 1$

Z drugiej strony, ustalić i pozwolić być elementem , który nie względnie pierwsze do . W tym przypadku istnieje liczba pierwsza taka że a . Jeśli dopuszczone do Liczba odwrotna modulo (nazwijmy go ), musielibyśmy że , co oznacza, że , a więc , więc . Od podążamy za tyma Z n n p p ∣ a p ∣ n a n b a ⋅ n b = 1 a ⋅ $n > 1$$a$$Z_n$$n$$p$$p \mid a$$p \mid n$$a$$n$$b$$a \cdot_n b = 1$( a ⋅ b - 1 $a \cdot b\:\%\:n = 1$n ∣ a ⋅ b - 1 p ∣ a p ∣ a ⋅ b p ∣ n p ∣ a ⋅ b - 1 p ∣ ( a ⋅ b ) - ( a ⋅ b - 1 ) = 1 $(a \cdot b - 1)\:\%\:n = a \cdot b\:\%\:n - 1 = 0$$n \mid a \cdot b - 1$$p \mid a$$p \mid a \cdot b$ . Z drugiej strony, ponieważ , podążamy również za tym . W ten sposób , co jest sprzeczne z założeniem, że jest liczbą pierwszą.$p \mid n$$p \mid a \cdot b - 1$$p \mid (a \cdot b) - (a \cdot b - 1) = 1$$p$

Dowodzi to, że następujące instrukcje są równoważne, gdy .$n > 1$

• $a$ i są chronione prawem autorskim.$n$

• $a$przyznaje zwielokrotniony odwrotny modulo .$n$

• $a$przyznaje się wyjątkową Liczba odwrotna modulo .$n$

Jak to działa

Dla każdej pary liczb całkowitych i w , liczba całkowita jest unikalny; W rzeczywistości, i są iloraz i pozostałą podzielone przez , to znaczy podane , można odzyskać , a , gdzie oznacza całkowitą podział. Na koniec, ponieważ i , jest elementem ; w rzeczywistości .b Z n k : = a ⋅ n + b a b k n k a = k / n b = $a$$b$$Z_n$$k := a \cdot n + b$$a$$b$$k$$n$$k$$a = k/n$/ a ≤ n - 1 b ≤ n - 1 k Z n 2 k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n 2 - $b = k\:\%\: n$$/$$a ≤ n - 1$$b ≤ n - 1$$k$$Z_{n^2}$$k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1$

Jak wspomniano powyżej, jeśli i są koprime, będzie unikalny taki że , tzn. Będzie unikalny taki, że i , tak więc generowany lista zawiera dokładnie raz.n b a ⋅ $a$$n$$b$k k / n = a k / n ⋅ $a \cdot b\:\%\:n = 1$$k$$k / n = a$$k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1$$a$

I odwrotnie, jeśli i nie są kopiami zapasowymi, warunek będzie fałszem dla wszystkich wartości takich, że , więc wygenerowana lista nie będzie zawierać .n k / n ⋅ $a$$n$k a = k / n $k / n \cdot k\:\%\:n = 1$$k$$a = k / n$$a$

Dowodzi to, że lista się lambda powraca będzie zawierać wszystkie coprimes „s w dokładnie raz.Z $n$$Z_n$

Galaretka , 4 bajty

gRỊT

Wypróbuj online!

Jak to działa

gRỊT  Main link. Argument: n

 R    Range; yield [1, ..., n].
g     Compute the GCD of n and each k in [1, ..., n].
  Ị   Insignificant; return 1 for GCDs less or equal to 1.
   T  Truth; yield the indices of all truthy elements.

Mathematica, 25 bajtów

Range@#~GCD~#~Position~1&

Nieco dziwny format wyjściowy, w którym każdy wynik jest zawinięty na osobnej liście, np {{1}, {3}, {7}, {9}}. Jeśli to nie w porządku, mam dwa rozwiązania o wielkości 30 bajtów:

Select[Range[x=#],#~GCD~x<2&]&
#&@@@Range@#~GCD~#~Position~1&

Mathematica faktycznie ma, CoprimeQale to zdecydowanie za długo.

2sable , 4 bajty

Kod:

ƒN¿–

Wyjaśnienie:

ƒ       # For N in the range [0, input]..
 N¿     #   Compute the GCD of N and the input
   –    #   If 1, print N with a newline

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Python, 93 82 74 bajty

f=lambda a,b:f(b,a%b)if b else a<2
lambda c:[i for i in range(c)if f(i,c)]

frekurencyjnie sprawdza, czy istnieją kopie zapasowe, a druga lambda je generuje. Wyświetla listę.

Właściwie 8 bajtów

;╗R`╜┤`░

Wypróbuj online!

Wyjaśnienie:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime

MATL , 7 bajtów

:GZd1=f

Wypróbuj online!

MATLAB / Octave, 22 bajty

@(n)find(gcd(1:n,n)<2)

Wypróbuj online!

JavaScript (ES6), 64 61 bajtów

Zaoszczędzono 3 bajty dzięki @ user81655

n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

Testowy fragment kodu

f=n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

for(var i = 2; i < 50; i++) console.log(i + ":", `[${ f(i) }]`);

Meduza , 19 18 bajtów

p
[#
`B
&~xr1
NnEi

Działa to poprzez obliczenie faktoryzacji pierwotnej każdej liczby w zakresie i sprawdzenie, czy przecina ona liczbę wejściową (Meduza nie ma jeszcze wbudowanej gcd). Ze względów golfowych dane wyjściowe są malejące. Wypróbuj online!

Wyjaśnienie

Po pierwsze, ioceniane jest wejście; dla danych wejściowych 10wartość i-cell wynosi 10.

r1
i

Tutaj r(zakres) jest stosowany do wejścia i 1. Ponieważ dane wejściowe są większe niż 1, zakres jest w kolejności malejącej; dla danych wejściowych 10daje to [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Ta część jest jedną dużą funkcją, która jest oceniana w ipowyższym zakresie.

~x
n

Przecięcie ( n) czynników pierwszych ( x).

&~x
Nn

Czy to jest puste ( N)

`
&~x
Nn

Wątek do poziomu 0, testowanie każdego elementu zakresu.

[#
`B
&~x
Nn

Filtruj ( #) zakres w odniesieniu do tej listy wartości logicznych. Funkcja stworzona przez [chce chce użyć argumentu #jako własnego argumentu, więc ustawiamy Bblokowanie #przed otrzymywaniem jakichkolwiek argumentów. W przeciwnym razie wartość ~-cell byłaby użyta jako argument dużej funkcji. Na koniec pdrukuje wynik.

Skumulowane, niekonkurencyjne, 24 21 bajtów

Zaoszczędzono 3 bajty, zainspirowane rubinem Borsunho . ( 1 eqdo 2<)

{!n:>1+:n gcd 2<keep}

Wypróbuj tutaj!

Jest to n-lambda, która przyjmuje pojedynczy argument i zwraca tablicę.

{!n:>1+:n gcd 2<keep}
{!                  }  n-lambda
  n                    push n
   :>                  range [0, n)
     1+                range [1, n]
       :               duplicate
        n gcd          element-wise gcd with n
              2<       element-wise equality with 1
                       this yields the range [1, n] and a boolean mask of coprime numbers
                keep   then, we simply apply the mask to the range and keep coprimes.

CJam , 14 bajtów

{:X{Xmff%:*},}

Wypróbuj online!

Wyjaśnienie

Nie musimy sprawdzać wszystkich możliwych dzielników ai btestować, czy są chronione prawem autorskim. To wystarczy spojrzeć, czy którykolwiek z głównych czynników bpodziałami a.

:X     e# Store the input in X.
{      e# Filter the list [0 1 ... X-1] by the results of this block...
  Xmf  e#   Get the prime factors of X.
  f%   e#   Take the current value modulo each of those prime factors.
  :*   e#   Multiply the results. Iff any of them divide the current
       e#   value, there's a 0 in the list, and the result of the product
       e#   is also 0, dropping the value from the resulting list.
},

Mathematica, 26 bajtów

Pick[r=Range@#,r~GCD~#,1]&

Perl 6 , 20 bajtów

{grep 2>* gcd$_,^$_}

Brachylog , 16 13 bajtów

>.$p'(e:A*?),

Jest to funkcja, która przyjmuje N jako dane wejściowe i generuje wszystkie liczby całkowite mniejsze niż i kopiuje do niej.

Wypróbuj online! Jak to często bywa w Brachylog, dodano do niego dodatkowy kod, aby uczynić tę funkcję pełnym programem; Interpreter Brachylog, jeśli otrzyma funkcję zamiast pełnego programu, uruchomi ją, ale nie wydrukuje wyniku, co oznacza, że ​​tak naprawdę nie można obserwować jego działania.

Wyjaśnienie:

Program Brachylog jest łańcuchem ograniczeń; zazwyczaj LHS jednego ograniczenia jest RHS następnego.

>.$p'(e:A*?),
>              The input is greater than
 .             the output, whose
  $p           prime factorisation does
    '(     )   not obey the following constraint:
      e        it has an element which
       :A*     can be multiplied by something to
          ?    produce the input.
            ,  (This comma turns off an unwanted implicit constraint.)

Zanotowałem trzy znaki, zdając sobie sprawę, że nie ma powodu, aby sprawdzać, czy wspólny czynnik (który jest już znany jako czynnik wyjściowy) jest pierwszym czynnikiem wejściowym. Wiemy już, że jest to liczba pierwsza, więc możemy po prostu sprawdzić, czy to czynnik. Jestem mile zaskoczony, że :A*?nie wysyła interpretera do nieskończonej pętli i nie pozwala na wartość całkowitą dla A , ale ponieważ interpreter robi to, co chcę, wezmę to.

Dyalog APL, 10 bajtów .

0~⍨⍳×1=⊢∨⍳

Objaśnienie (wejście n):

0~⍨⍳×1=⊢∨⍳
         ⍳ - 1 ... n (Thus, ⎕IO is 1)
       ⊢∨  - Each GCD'd by n
     1=    - Test equality with 1 on each element
   ⍳×      - multiplied by its index
0~⍨        - without 0.

Japt -f , 9 8 5 2 bajty

jN

Spróbuj

• 2 bajty zaoszczędzone dzięki ETH wskazując fart mózgowy, co doprowadziło do zapisania kolejnego bajtu.

Mathematica, 33 bajty

xSelect[Range@x,x~CoprimeQ~#&]

Zawiera U + F4A1

Haskell, 27 bajtów

f n=[k|k<-[1..n],gcd n k<2]

Wypróbuj online!

Julia 0,5 , 23 bajty

!n=1÷gcd.(1:n,n)|>find

Wypróbuj online!

memy , 11 bajtów niekonkurujących , nieaktualne

Niekonkurencyjne, ponieważ iteracja STDIN jest nowa. Wykorzystuje kodowanie UTF-8.

d`}}]i=1?ip

Wyjaśnienie:

d     Set program to not output result
`}    Loop next input-times
}]i   GCD of input and loop index
=1?   Is it equal to 1? If yes,
ip    Print out loop index

}uzyskuje dostęp do następnego elementu wejściowego, ale ostatnie wejście jest zapętlone, gdy jest podane, więc wprowadzanie 6spowoduje jak 6 6 6 6 6 ...w STDIN, umożliwiając odczyt dwóch wyjść z jednego.

05AB1E , 3 bajty

Lʒ¿

Wypróbuj online!

Ma nowe funkcje.

Ruby, 36 34

->n{n.times{|i|p i if i.gcd(n)<2}}

Trzeba przyznać, że nie jest to bardzo inspirująca odpowiedź.

2 bajty zapisane dzięki Conorowi O'Brienowi.

Python 3 , 60 bajtów

Importuje gcd zamiast pisać dla niego nową lambda. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]

Julia, 30 bajtów

n->filter(x->(gcd(n,x)<2),1:n)

Funkcja anonimowa. filterusuwa elementy z listy, które nie są zgodne z prawdą według funkcji.

W tym przypadku funkcją jest x->(gcd(n,x)<2)(prawda, jeśli gcd wejścia i elementu listy jest mniejsza niż 2). Lista jest zakresem 1:n.

PARI / GP , 27 bajtów

n->[k|k<-[1..n],gcd(k,n)<2]

Wykorzystuje to zestaw notacji wprowadzony w wersji 2.6.0 (2013). We wcześniejszych wersjach potrzebne były jeszcze cztery bajty:

n->select(k->gcd(k,n)<2,[1..n])

byłoby potrzebne.

05AB1E , 4 bajty

GN¿–

Wypróbuj online!

Jak to działa

     # implicit input
G    # for N in range(1..input)
 N   # push N
  ¿  # gcd(input, N)
   – # if 1, print N

C (gcc) , 54 bajty

k;f(n){for(k=0;++k/n<n;k/n*k%n-1||printf("%u ",k/n));}

To jest port mojej odpowiedzi w Pythonie .

Wypróbuj online!

Pyth , 5 bajtów

x1iLQ

Wypróbuj online!

Jak to działa

Zauważ, że Pyth używa indeksowania 0.

x1iLQ   Q = eval(input())

x1iLQQ  implicit Q at the end
  iLQQ  [gcd(Q,0), gcd(Q,1), ..., gcd(Q,Q-1)]
x1      all occurences of 1 in the above list (return their indices)