Biorąc pod uwagę liczbę n >= 2
, wypisz wszystkie dodatnie liczby całkowite mniejsze niż n
gdzie gcd(n, k) == 1
(przy k
czym jest to jedna z liczb wyjściowych). Numery tego rodzaju są względnie pierwsze dla siebie.
Przykład: 10
podaje 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, n
któ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.
code-golf
math
number-theory
primes
Rɪᴋᴇʀ
źródło
źródło
1\n3\n
) Liczą się jako prawidłowe dane wyjściowe?Odpowiedzi:
Galaretka , 3 bajty
Wypróbuj online!
Jak to działa?
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):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[ 1 , wejście ] 1 1gcd ( 1 , x ) = 1∀x ∈ Z∗ 1
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 ∣ yx , y∈ Z∗ y= x + 1 k k ∣ x k ∣ 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 1k ∣ ( y- x ) k ∣ ( x + 1 - x ) k ∣ 1 1 1
źródło
ÐṂ
istniały wtedy, w każdym razie jestem z tego całkiem zadowolony.DṂ
istniało, ale działało tylko w przypadku monad. Commit wdrożoneÞ
,ÐṂ
,ÐṀ
dla dyads jest datowany 9 maja 2017Python 2 ,
6147 bajtówWypró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 )( Zn, +n,⋅n) n Zn={0,…,n−1} a ⋅ n b = a ⋅ ba+nb=(a+b)%n + ,a ⋅nb = a ⋅ b%n + ,⋅ i %
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 = 1za b Zn n 1a ⋅nb = 1%n n > 11%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 ⋅ xn > 1 za n Zn a ⋅nx = a ⋅ny x y Zn a ⋅ ( x - y )a ⋅ x%n = a ⋅ 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 Za ⋅ ( x - y)%n = a ⋅ x%n - a ⋅ y%n = 0 n ∣ a ⋅ ( x - y) n a ⋅ ( x - y) n za n ∣ 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⋅n0,…,a⋅n(n−1) Zn Zn n 1 b a ⋅ n b = 1Zn a⋅nb=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 ⋅ bn>1 a Zn n p p∣a p∣n a n b a⋅nb=1 ( a ⋅ b - 1 )a⋅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 p(a⋅b−1)%n=a⋅b%n−1=0 n∣a⋅b−1 p∣a p∣a⋅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∣n p∣a⋅b−1 p∣(a⋅b)−(a⋅b−1)=1 p
Dowodzi to, że następujące instrukcje są równoważne, gdy .n>1
na i są chronione prawem autorskim.n
na przyznaje zwielokrotniony odwrotny modulo .n
na 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 = ka b Zn k:=a⋅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 - 1b=k%n / a≤n−1 b≤n−1 k Zn2 k≤(n−1)⋅n+(n−1)=n2−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 ⋅ ba n b k k / n = a k / n ⋅ ka⋅b%n=1 k k/n=a ak/n⋅k%n=(k/n)⋅(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 ⋅ ka n k a = k / n ak/n⋅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 nn Zn
źródło
Galaretka , 4 bajty
Wypróbuj online!
Jak to działa
źródło
gRỊT
ÐṂ
), aby uzyskać 3 bajty .Mathematica, 25 bajtów
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:Mathematica faktycznie ma,
CoprimeQ
ale to zdecydowanie za długo.źródło
Q
oznacza wCoprimeQ
?EvenQ
,PrimeQ
lubSubsetQ
.2sable , 4 bajty
Kod:
Wyjaśnienie:
Wykorzystuje kodowanie CP-1252 . Wypróbuj online!
źródło
Python,
938274 bajtyf
rekurencyjnie sprawdza, czy istnieją kopie zapasowe, a druga lambda je generuje. Wyświetla listę.źródło
Właściwie 8 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
range(1, n)
jeśli pozwoli to zaoszczędzić jakieś bajty.R
(range(1, n+1)
) ir
(range(n)
). Ponieważ są one równoważne, wybrałemR
(ponieważ przypadkowo uderzyłem Caps Lock podczas pisania kodu).MATL , 7 bajtów
Wypróbuj online!
źródło
MATLAB / Octave, 22 bajty
Wypróbuj online!
źródło
JavaScript (ES6),
6461 bajtówZaoszczędzono 3 bajty dzięki @ user81655
Testowy fragment kodu
źródło
a==
za<2
?a
w pewnym momencie może być 0. Będę musiał sprawdzićfilter
aby usunąć potrzebę otrzymaniab
parametru:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
Meduza ,
1918 bajtówDział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,
i
oceniane jest wejście; dla danych wejściowych10
wartośći
-cell wynosi10
.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ściowych10
daje to[9 8 7 6 5 4 3 2 1]
.Ta część jest jedną dużą funkcją, która jest oceniana w
i
powyższym zakresie.Przecięcie (
n
) czynników pierwszych (x
).Czy to jest puste (
N
)Wątek do poziomu 0, testowanie każdego elementu zakresu.
Filtruj (
#
) zakres w odniesieniu do tej listy wartości logicznych. Funkcja stworzona przez[
chce chce użyć argumentu#
jako własnego argumentu, więc ustawiamyB
blokowanie#
przed otrzymywaniem jakichkolwiek argumentów. W przeciwnym razie wartość~
-cell byłaby użyta jako argument dużej funkcji. Na koniecp
drukuje wynik.źródło
Skumulowane, niekonkurencyjne,
2421 bajtówZaoszczędzono 3 bajty, zainspirowane rubinem Borsunho . (
1 eq
do2<
)Wypróbuj tutaj!
Jest to n-lambda, która przyjmuje pojedynczy argument i zwraca tablicę.
źródło
keep
nie działał ładnie.CJam , 14 bajtów
Wypróbuj online!
Wyjaśnienie
Nie musimy sprawdzać wszystkich możliwych dzielników
a
ib
testować, czy są chronione prawem autorskim. To wystarczy spojrzeć, czy którykolwiek z głównych czynnikówb
podziałamia
.źródło
Mathematica, 26 bajtów
źródło
Perl 6 , 20 bajtów
źródło
Brachylog ,
1613 bajtówJest 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.
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.źródło
Dyalog APL, 10 bajtów .
Objaśnienie (wejście
n
):źródło
⍨
Japt
-f
,9852 bajtySpróbuj
źródło
o f_jU
j
można go również użyć do sprawdzenia, czy 2 liczby są pierwszymi.Mathematica, 33 bajty
Zawiera U + F4A1
źródło
Haskell, 27 bajtów
Wypróbuj online!
źródło
Julia 0,5 , 23 bajty
Wypróbuj online!
źródło
memy , 11 bajtów niekonkurujących , nieaktualne
Niekonkurencyjne, ponieważ iteracja STDIN jest nowa. Wykorzystuje kodowanie UTF-8.
Wyjaśnienie:
}
uzyskuje dostęp do następnego elementu wejściowego, ale ostatnie wejście jest zapętlone, gdy jest podane, więc wprowadzanie6
spowoduje jak6 6 6 6 6 ...
w STDIN, umożliwiając odczyt dwóch wyjść z jednego.źródło
05AB1E , 3 bajty
Wypróbuj online!
Ma nowe funkcje.
źródło
Ruby,
3634Trzeba przyznać, że nie jest to bardzo inspirująca odpowiedź.
2 bajty zapisane dzięki Conorowi O'Brienowi.
źródło
(n)
Python 3 , 60 bajtów
Importuje gcd zamiast pisać dla niego nową lambda. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
źródło
Julia, 30 bajtów
Funkcja anonimowa.
filter
usuwa 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 zakresem1:n
.źródło
PARI / GP , 27 bajtów
Wykorzystuje to zestaw notacji wprowadzony w wersji 2.6.0 (2013). We wcześniejszych wersjach potrzebne były jeszcze cztery bajty:
byłoby potrzebne.
źródło
[1..n]
), sprawdź, czy gcd ma wartość 1 (gcd(n,k)<2
), zwróć liczby z tą właściwością. Jest->
to notacja funkcji / zamknięcia, krótsza o 2 bajty niż normalna składnia funkcji i[...|...<-...,...]
jest to notacja zestawu wyjaśniona w odpowiedzi (patrz rozdział 2.3.14 w Instrukcji użytkownika lub wyszukaj<-
).05AB1E , 4 bajty
Wypróbuj online!
Jak to działa
źródło
C (gcc) , 54 bajty
To jest port mojej odpowiedzi w Pythonie .
Wypróbuj online!
źródło
Pyth , 5 bajtów
Wypróbuj online!
Jak to działa
Zauważ, że Pyth używa indeksowania 0.
źródło