Étant donné un nombre n >= 2, indiquez tous les entiers positifs inférieurs à noù gcd(n, k) == 1(avec kl'un des nombres en sortie). Les nombres de ce type sont coprimes les uns aux autres.

Exemple: 10donne le résultat [1, 3, 7, 9](sous la forme de votre choix, à condition que les nombres soient séparés de manière non ambiguë et dans une sorte de liste). La liste ne peut pas avoir des entrées en double et ne doit pas être triée.

Plus de cas de test:

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]

Nous ne comptons pas non plus les chiffres ci n- dessus qui sont coprime n, uniquement parce que je suis à peu près certain que les solutions sont infinies.

A noter également: les nombres coprimes l'un par rapport à l'autre sont également dits relativement premiers ou mutuellement premiers l'un par rapport à l'autre.

Gelée , 3 octets

gÐṂ

Essayez-le en ligne!

Comment cela marche-t-il?

gÐṂ - (Monadic) Programme complet.

g - Le plus grand commun diviseur.
 - Conserve les éléments avec une valeur de lien minimale (c'est-à-dire ceux avec GCD == 1)
       Notez que cela crée automatiquement la plage [1, entrée] (incluse).

Preuve de validité

Puisque nous voulons extraire uniquement les coprimes, la valeur minimale de la liste des plus grands diviseurs communs doit être 1 pour que l’ ÐṂastuce fonctionne. Prouvons cela (de deux manières différentes):

1. $[1, \text{input}]$$1$$\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{*}$$1$

2. Deux entiers positifs consécutifs sont toujours coprimes. Considérons , avec . On prend ensuite un autre entier positif tel que et . y = x + 1 k k | x k | $x, y \in \mathbb{Z}^{*}$$y = x + 1$$k$$k \mid x$$k \mid y$

   Cela implique que , donc , donc . Le seul entier positif à diviser est lui-même, il est donc garanti qu'il apparaisse dans la liste et sera toujours la valeur minimale.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 octets

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

Essayez-le en ligne!

Contexte

Considérons l' anneau . Bien que cet anneau soit généralement défini à l'aide de classes de résidus modulo n , il peut également être considéré comme l'ensemble Z n = { 0 , … , n - 1 } , où les opérateurs d'addition et de multiplication sont définis par a + n b = ( a + b $(Z_n, +_n, \cdot_n)$$n$$Z_n = \{0, \dots, n - 1\}$ et, oùdésignent les opérateurs habituels d'addition, de multiplication et de modulo sur les entiers.$a +_n b = (a + b)\:\%\: n$+ $a \cdot_n b = a \cdot b\:\%\: n$$+,\:\cdot\text{, and } \%$

Deux éléments et de sont appelés inverses multiplicatifs mutuels modulo si . Notez que lorsque .$a$$b$$Z_n$$n$$a \cdot_n b = 1\:\%\:n$$1\:\%\:n = 1$$n > 1$

Fixez et laissez être un coprime de n dans Z n . Si un ⋅ n x = a ⋅ n y pour deux éléments x et y de Z n , nous avons que un ⋅ x$n > 1$$a$$n$$Z_n$$a \cdot_n x = a \cdot_n y$$x$$y$$Z_n$ . Cela implique que un ⋅ ( x - y $a \cdot x\:\%\:n = a \cdot y\:\%\:n$ , et on suit que n | a ⋅ ( x - y ) ,savoir, n divise une ⋅ ( x - y ) uniformément. Puisque n ne partage pas les diviseurs premiers avec a , cela signifie que n ∣ x - y . Enfin, comme - n < x - y < n , nous concluons que x = y . Cela montre que les produits d' une $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$$x = y$ sont tous des éléments différents de Z n . Puisque Z n a exactement n éléments, un (et exactement un) de ces produits doit être égal à 1 , c’est-à-dire qu’il existe ununique b dans Z n tel que a ⋅ n b = 1 .$a \cdot_n 0, \dots, a \cdot_n (n - 1)$$Z_n$$Z_n$$n$$1$ $b$$Z_n$$a \cdot_n b = 1$

A l' inverse, fix et laisser un être un élément de Z n qui est pas coprime à n . Dans ce cas, il existe un nombre premier p tel que p ∣ a et p ∣ n . Si a admettait un modulo inverse multiplicatif n (appelons-le b ), nous aurions que a ⋅ n b = 1 , ce qui signifie que a ⋅ $n > 1$$a$$Z_n$$n$$p$$p \mid a$$p \mid n$$a$$n$$b$$a \cdot_n b = 1$ et donc ( a ⋅ b - 1 $a \cdot b\:\%\:n = 1$ , donc n ∣ a ⋅ b - 1 . Depuis p ∣ a , on suit que p ∣ a ⋅ b . D'autre part, depuis p ∣ n , nous suivons également celui de p ∣ a ⋅ b - 1 . De cette façon, p ∣ ( a ⋅ b ) - ( a ⋅ b - 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$$p \mid n$$p \mid a \cdot b - 1$$p \mid (a \cdot b) - (a \cdot b - 1) = 1$, ce qui contredit l'hypothèse selon laquelle est un nombre premier.$p$

Cela prouve que les déclarations suivantes sont équivalentes lorsque .$n > 1$

• et n sont coprimes.$a$$n$

• admet un inverse multiplicatif modulo n .$a$$n$

• admet ununiqueinverse multiplicatif modulo n .$a$$n$

Comment ça fonctionne

Pour chaque couple d'entiers et b dans Z n , l'entier k : = a ⋅ n + b est unique; en fait, a et b sont des quotients et le reste de k divisé par n , c'est-à-dire, étant donné k , on peut récupérer a = k / n et b = $a$$b$$Z_n$$k := a \cdot n + b$$a$$b$$k$$n$$k$$a = k/n$ , où / désigne ladivisionentière. Enfin, puisque a ≤ n - 1 et b ≤ n - 1 , k est un élément de Z n 2 ; en fait, k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n deux - 1 .$b = k\:\%\: n$$/$$a ≤ n - 1$$b ≤ n - 1$$k$$Z_{n^2}$$k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1$

Comme indiqué ci-dessus, si et n sont des coprimes, il y aura un unique b tel que a ⋅ $a$$n$$b$ , c'est-à-dire qu'il y aura un unique k tel que k / n = a et k / n ⋅ $a \cdot b\:\%\:n = 1$$k$$k / n = a$ , la liste produite contiendra une seule fois.$k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1$$a$

A l' inverse, si et n sont pas coprime, la condition k / n ⋅ $a$$n$ sera faux pour toutes les valeurs de k telles que a = k / n , de sorte que la liste généréenecontiendrapas a .$k / n \cdot k\:\%\:n = 1$$k$$a = k / n$$a$

Cela prouve que la liste des lambda déclarations contiennent tous de » Les premiers entre eux dans Z n exactement une fois.$n$$Z_n$

Gelée , 4 octets

gRỊT

Essayez-le en ligne!

Comment ça fonctionne

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 octets

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

Format de sortie légèrement étrange, où chaque résultat est encapsulé dans une liste séparée, par exemple {{1}, {3}, {7}, {9}}. Si cela ne vous convient pas, j'ai deux solutions à 30 octets:

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

Mathematica l'a fait CoprimeQmais c'est beaucoup trop long.

2sable , 4 octets

Code:

ƒN¿–

Explication:

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

Utilise le codage CP-1252 . Essayez-le en ligne!

Python, 93 82 74 octets

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

fvérifie récursivement les coprimes, et le second lambda les génère. Affiche une liste.

En fait , 8 octets

;╗R`╜┤`░

Essayez-le en ligne!

Explication:

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

MATL , 7 octets

:GZd1=f

Essayez-le en ligne!

MATLAB / Octave, 22 octets

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

Essayez-le en ligne!

JavaScript (ES6), 64 61 octets

3 octets sauvegardés grâce à @ user81655

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

Extrait de test

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

Méduse , 19 à 18 octets

p
[#
`B
&~xr1
NnEi

Cela fonctionne en calculant la factorisation première de chaque nombre dans la plage et en vérifiant si elle recoupe celle de l'entrée (Jellyfish n'a pas encore de gcd intégré). Pour des raisons de golf, la sortie est dans l'ordre décroissant. Essayez-le en ligne!

Explication

Tout d'abord, iest évalué l'entrée; pour l'entrée 10, la valeur de la i-cell est 10.

r1
i

Ici r(plage) est appliqué à l'entrée et 1. Comme l'entrée est supérieure à 1, la plage est dans l'ordre décroissant; pour l'entrée 10, cela donne [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Cette partie est une grande fonction, qui est évaluée sur iet la plage ci-dessus.

~x
n

Intersection ( n) des facteurs premiers ( x).

&~x
Nn

Est-ce vide? ( N)

`
&~x
Nn

Fil au niveau 0, testant pour chaque élément de la gamme.

[#
`B
&~x
Nn

Filtrer ( #) la plage par rapport à cette liste de booléens. La fonction produite par [veut utiliser l'argument à #comme son propre argument, nous avons donc Bbloqué l' #obtention de tous les arguments. Sinon, la valeur de ~-cell serait utilisée comme argument de la grande fonction. Enfin, paffiche le résultat.

Empilé, non compétitif, 24 21 octets

Sauvé 3 octets, inspiré par le rubis de Borsunho . ( 1 eqà 2<)

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

Essayez-le ici!

C'est un n-lambda qui prend un seul argument et donne le tableau.

{!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 octets

{:X{Xmff%:*},}

Essayez-le en ligne!

Explication

Nous n'avons pas besoin de vérifier tous les diviseurs possibles de aet bde vérifier s'ils sont coprimes. Il suffit de regarder si l'un des facteurs premiers des bdivisions 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 octets

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

Perl 6 , 20 octets

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

Brachylog , 16 à 13 octets

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

C'est une fonction qui prend N en entrée et génère tous les entiers inférieurs et égaux à celle-ci.

Essayez-le en ligne! Comme souvent dans Brachylog, un code supplémentaire a été ajouté pour que la fonction devienne un programme complet. L'interprète de Brachylog, s'il reçoit une fonction plutôt qu'un programme complet, l'exécutera mais n'imprimera pas la sortie, ce qui signifie que vous ne pouvez pas vraiment en observer le fonctionnement.

Explication:

Un programme Brachylog est une chaîne de contraintes; généralement, le LHS d'une contrainte est le RHS de la suivante.

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

Détruit trois personnages en réalisant qu'il n'y a aucune raison de vérifier si le facteur commun (qui est déjà connu pour être un facteur premier de la sortie) est un facteur premier de l'entrée. Nous savons déjà que c'est primordial, alors nous pouvons simplement vérifier si c'est un facteur. Je suis agréablement surpris par le :A*?fait que l'interprète n'est pas envoyé dans une boucle infinie et ne permet pas une valeur non entière pour A , mais si l'interprète fait ce que je veux, je le prendrai.

Dyalog APL, 10 octets .

0~⍨⍳×1=⊢∨⍳

Explication (entrée 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 octets

jN

L'essayer

• 2 octets sauvegardés grâce à l' ETH indiquant un brainfart, ce qui a conduit à la création d'un autre octet.

Mathematica, 33 octets

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

Contient U + F4A1

Haskell, 27 octets

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

Essayez-le en ligne!

Julia 0.5 , 23 octets

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

Essayez-le en ligne!

mèmes , 11 octets non concurrents , obsolètes

L'itération de STDIN non concurrente est nouvelle. Utilise le codage UTF-8.

d`}}]i=1?ip

Explication:

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

}accède au prochain élément d’entrée, mais la dernière entrée est bouclée lorsqu’elle est donnée, l’entrée 6sera alors 6 6 6 6 6 ...identique à celle de STDIN, ce qui permettra de lire deux sorties à la fois.

05AB1E , 3 octets

Lʒ¿

Essayez-le en ligne!

A de nouvelles fonctionnalités.

Ruby, 36 34

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

Certes, cette réponse n’est pas très inspirée .

2 octets économisés grâce à Conor O'Brien.

Python 3 , 60 octets

Importe gcd au lieu d’écrire un nouveau lambda. Les suggestions de golf sont les bienvenues. Essayez-le en ligne!

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

Julia, 30 octets

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

Fonction anonyme. filtersupprime les éléments d'une liste qui ne sont pas conformes à une fonction.

Dans ce cas, la fonction est x->(gcd(n,x)<2)(true si le gcd de l'entrée et l'élément de liste sont inférieurs à 2). La liste est la gamme 1:n.

PARI / GP , 27 octets

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

Ceci utilise la notation de jeu introduite dans la version 2.6.0 (2013). Dans les versions précédentes, quatre octets supplémentaires étaient nécessaires:

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

serait nécessaire.

05AB1E , 4 octets

GN¿–

Essayez-le en ligne!

Comment ça fonctionne

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

C (gcc) , 54 octets

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

Ceci est un portage de ma réponse en Python .

Essayez-le en ligne!

Pyth , 5 octets

x1iLQ

Essayez-le en ligne!

Comment ça fonctionne

Notez que Pyth utilise l'indexation 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)