다수 주어 n >= 2,보다 출력이 모두 양의 정수 n여기서, gcd(n, k) == 1(함께 k출력 번호 중 어느 하나 인). 이런 종류의 숫자는 서로 동일 합니다.

예 : 10출력을 제공합니다 [1, 3, 7, 9](숫자가 명확하게 분리되어 있고 목록에있는 한 원하는 형식으로). 목록은 중복 된 항목을 가질 수 없으며 정렬 할 필요가 없습니다.

더 많은 테스트 사례 :

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]

우리는 또한 무한한 해결책이 있다고 확신하기 때문에 ncoprime 인 위의 숫자를 세지 않습니다 n.

또한 참고 : 서로 공통된 숫자는 상대적으로 소수이거나 서로 소수입니다.

답변

젤리 , 3 바이트

gÐṂ

온라인으로 사용해보십시오!

어떻게 작동합니까?

gÐṂ-(Monadic) 전체 프로그램.

g-최대 공약수
 ÐṂ-링크 값을 최소로 유지하십시오 (예 : GCD == 1 인 요소)
       그러면 범위 [1, 입력] (포함)이 자동으로 생성됩니다.

유효성 증명

우리는 단지 coprimes을 추출 할 이후 가장 큰-공통 약수 목록의 최소값 이 될 1 에 대한 ÐṂ트릭이 작동합니다. 이를 두 가지 방법으로 증명해 보자.

내재적으로 생성 된 범위 에는 및 됩니다. 최대 공약수는 항상 양의 정수이므로 은 항상 발생하며 항상 최소값이됩니다. $[1, input]$
$[1, input]$
$[1, \text{input}]$ $1$
$1$
$1$ $gcd (1, x) = 1 \forall x \in Z^{*}$
$gcd (1, x) = 1 \forall x \in Z^{*}$
$\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{*}$ $1$
$1$
$1$
두 개의 연속 양의 정수는 항상 coprime입니다. 고려 와 . 그런 다음 및 와 같은 또 다른 양의 정수 취 합니다. $x, y \in Z^{*}$
$x, y \in Z^{*}$
$x, y \in \mathbb{Z}^{*}$ $y = x + 1$
$y = x + 1$
$y = x + 1$ $k$
$k$
$k$ $k ∣ x$
$k ∣ x$
$k \mid x$ $k ∣ y$
$k ∣ y$
$k \mid y$

이것은 이므로 이므로 입니다. 을 나누는 유일한 양의 정수 는 자체이므로 목록에 표시되며 항상 최소값이됩니다. $k ∣ (y - x)$
$k ∣ (y - x)$
$k \mid (y - x)$ $k ∣ (x + 1 - x)$
$k ∣ (x + 1 - x)$
$k \mid (x + 1 - x)$ $k ∣ 1$
$k ∣ 1$
$k \mid 1$ $1$
$1$
$1$ $1$
$1$
$1$

답변

파이썬 2 , 61 47 바이트

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

온라인으로 사용해보십시오!

배경

링 고려하십시오 . 이 고리는 일반적으로 모듈로 잔류 물 클래스를 사용하여 정의되지만 , 집합으로 간주 될 수 있습니다 . 여기에서 더하기 및 곱하기 연산자는 및 , 여기서 는 일반적인 추가를 나타냅니다. 정수에 대한 곱셈과 모듈로 연산자. $(Z_{n}, +_{n}, \cdot_{n})$

(Z_{n}, +_{n}, \cdot_{n})

$(Z_n, +_n, \cdot_n)$ $n$

n

$n$ $Z_{n} = {0, \dots, n - 1}$

Z_{n} = {0, \dots, n - 1}

$Z_n = \{0, \dots, n - 1\}$ $a +_{n} b = (a + b) % n$

a +_{n} b = (a + b) % n

$a +_n b = (a + b)\:\%\: n$ $a \cdot_{n} b = a \cdot b % n$

a \cdot_{n} b = a \cdot b % n

$a \cdot_n b = a \cdot b\:\%\: n$ $+, \cdot, and %$

+, \cdot, and %

$+,\:\cdot\text{, and } \%$

두 요소 및 의 상호라고 곱셈 역관계 모듈로 경우 . 참고 마다 . $a$

a

$a$ $b$

b

$b$ $Z_{n}$

Z_{n}

$Z_n$ $n$

n

$n$ $a \cdot_{n} b = 1 % n$

a \cdot_{n} b = 1 % n

$a \cdot_n b = 1\:\%\:n$ $1 % n = 1$

1 % n = 1

$1\:\%\:n = 1$ $n > 1$

n > 1

$n > 1$

수정 및하자 의 서로 소가 될 에서 . 경우 개의 요소에 대한 및 의 , 우리가 그 . 이것은 의미가 , 우리는 다음과 즉, 균등하게 나눕니다 . 이후 과 공유 아무 주요 약수 이 그 의미 . 마지막으로 $n > 1$

n > 1

$n > 1$ $a$

a

$a$ $n$

n

$n$ $Z_{n}$

Z_{n}

$Z_n$ $a \cdot_{n} x = a \cdot_{n} y$

a \cdot_{n} x = a \cdot_{n} y

$a \cdot_n x = a \cdot_n y$ $x$

x

$x$ $y$

y

$y$ $Z_{n}$

Z_{n}

$Z_n$ $a \cdot x % n = a \cdot y % n$

a \cdot x % n = a \cdot y % n

$a \cdot x\:\%\:n = a \cdot y\:\%\:n$ $a \cdot (x - y) % n = a \cdot x % n - a \cdot y % n = 0$

a \cdot (x - y) % n = a \cdot x % n - a \cdot y % n = 0

$a \cdot (x - y)\:\%\:n = a \cdot x\:\%\:n - a \cdot y\:\%\:n = 0$ $n ∣ a \cdot (x - y)$

n ∣ a \cdot (x - y)

$n \mid a \cdot (x - y)$ $n$

n

$n$ $a \cdot (x - y)$

a \cdot (x - y)

$a \cdot (x - y)$ $n$

n

$n$ $a$

a

$a$ $n ∣ x - y$

n ∣ x - y

$n \mid x - y$ $- n < x - y < n$

- n < x - y < n

$-n < x - y < n$ , 우리는 라고 결론지었습니다 . 이는 제품 이 모두 다른 요소임을 . 이후 정확히 보유 요소 같아야 해당 제품의 온 (정확히 하나) 예를하는가 고유 에서 되도록 . $x = y$

x = y

$x = y$ $a \cdot_{n} 0, \dots, a \cdot_{n} (n - 1)$

a \cdot_{n} 0, \dots, a \cdot_{n} (n - 1)

$a \cdot_n 0, \dots, a \cdot_n (n - 1)$ $Z_{n}$

Z_{n}

$Z_n$ $Z_{n}$

Z_{n}

$Z_n$ $n$

n

$n$ $1$

1

$1$ $b$

b

$b$ $Z_{n}$

Z_{n}

$Z_n$ $a \cdot_{n} b = 1$

a \cdot_{n} b = 1

$a \cdot_n b = 1$

반대로, 수정 및하자 의 요소 수 되어 있지 에 서로 소 . 이 경우 및 과 같은 소수 있습니다. 경우 곱셈 역 모듈로 인정 (현실을 부르 자 , 우리가있는 것) , 의미가 , 따라서, 이므로 입니다. 이후 , 우리는 다음과 $n > 1$

n > 1

$n > 1$ $a$

a

$a$ $Z_{n}$

Z_{n}

$Z_n$ $n$

n

$n$ $p$

p

$p$ $p ∣ a$

p ∣ a

$p \mid a$ $p ∣ n$

p ∣ n

$p \mid n$ $a$

a

$a$ $n$

n

$n$ $b$

b

$b$ $a \cdot_{n} b = 1$

a \cdot_{n} b = 1

$a \cdot_n b = 1$ $a \cdot b % n = 1$

a \cdot b % n = 1

$a \cdot b\:\%\:n = 1$ $(a \cdot b - 1) % n = a \cdot b % n - 1 = 0$

(a \cdot b - 1) % n = a \cdot b % n - 1 = 0

$(a \cdot b - 1)\:\%\:n = a \cdot b\:\%\:n - 1 = 0$ $n ∣ a \cdot b - 1$

n ∣ a \cdot b - 1

$n \mid a \cdot b - 1$ $p ∣ a$

p ∣ a

$p \mid a$ $p ∣ a \cdot b$

p ∣ a \cdot b

$p \mid a \cdot b$ . 반면에 이기 때문에 도 따릅니다 . 이 방법으로 이므로 가 소수 라는 가정과 모순 됩니다. $p ∣ n$

p ∣ n

$p \mid n$ $p ∣ a \cdot b - 1$

p ∣ a \cdot b - 1

$p \mid a \cdot b - 1$ $p ∣ (a \cdot b) - (a \cdot b - 1) = 1$

p ∣ (a \cdot b) - (a \cdot b - 1) = 1

$p \mid (a \cdot b) - (a \cdot b - 1) = 1$ $p$

p

$p$

이는 때 다음 명령문이 동일 함을 증명합니다 . $n > 1$

n > 1

$n > 1$

$a$
$a$
$a$ 와 은 coprime입니다. $n$
$n$
$n$
$a$
$a$
$a$ 곱하기 역 모듈로 인정합니다 . $n$
$n$
$n$
$a$
$a$
$a$ 는 고유 한 곱셈 역 모듈로 인정합니다 . $n$
$n$
$n$

작동 원리

정수의 각 쌍 및 에 , 정수 고유; 실제로 와 는 몫이고 나머지를 으로 나눈 값 , 즉 가 주어지면 및 복구 할 수 있습니다 . 여기서 정수 나누기를 나타냅니다 . 마지막으로 이고 이므로 는 의 요소입니다 . 실제로 입니다. $a$

a

$a$ $b$

b

$b$ $Z_{n}$

Z_{n}

$Z_n$ $k := a \cdot n + b$

k := a \cdot n + b

$k := a \cdot n + b$ $a$

a

$a$ $b$

b

$b$ $k$

k

$k$ $n$

n

$n$ $k$

k

$k$ $a = k / n$

a = k / n

$a = k/n$ $b = k % n$

b = k % n

$b = k\:\%\: n$ $/$

/

$/$ $a \leq n - 1$

a \leq n - 1

$a ≤ n - 1$ $b \leq n - 1$

b \leq n - 1

$b ≤ n - 1$ $k$

k

$k$ $Z_{n^{2}}$

Z_{n^{2}}

$Z_{n^2}$ $k \leq (n - 1) \cdot n + (n - 1) = n^{2} - 1$

k \leq (n - 1) \cdot n + (n - 1) = n^{2} - 1

$k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1$

위에서 언급 한 바와 같이, 와 이 동일 프라임 인 경우 과 같은 고유 가있을 것입니다. 즉, 와 와 같은 고유 가있을 것입니다. , 이렇게 생성 된 목록에 포함 회만. $a$

a

$a$ $n$

n

$n$ $b$

b

$b$ $a \cdot b % n = 1$

a \cdot b % n = 1

$a \cdot b\:\%\:n = 1$ $k$

k

$k$ $k / n = a$

k / n = a

$k / n = a$ $k / n \cdot k % n = (k / n) \cdot (k % n) % n = 1$

k / n \cdot k % n = (k / n) \cdot (k % n) % n = 1

$k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1$ $a$

a

$a$

반대로, 와 이 동일 프라임 이 아닌 경우 은 모든 값에 대해 과 같이 거짓 이므로 생성 된 목록에 포함 되지 않습니다. . $a$

a

$a$ $n$

n

$n$ $k / n \cdot k % n = 1$

k / n \cdot k % n = 1

$k / n \cdot k\:\%\:n = 1$ $k$

k

$k$ $a = k / n$

a = k / n

$a = k / n$ $a$

a

$a$

이것은 람다 리턴이 Z_n에있는 의 모든 정확히 한 번 포함 할 것임을 증명합니다 . $n$

n

$n$ $Z_{n}$

Z_{n}

$Z_n$

답변

젤리 , 4 바이트

gRỊT

온라인으로 사용해보십시오!

작동 원리

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 바이트

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

약간 이상한 출력 형식으로 각 결과가 별도의 목록으로 래핑됩니다 (예 🙂 {{1}, {3}, {7}, {9}}. 그것이 좋지 않으면 30 바이트에 두 가지 해결책이 있습니다.

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

Mathematica는 실제로 가지고 CoprimeQ있지만 너무 길다.

답변

2sable , 4 바이트

암호:

ƒN¿–

설명:

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

CP-1252 인코딩을 사용합니다 . 온라인으로 사용해보십시오!

답변

파이썬, 93 82 74 바이트

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

f재귀 적으로 coprimes를 확인하고 두 번째 람다는 그것들을 생성합니다. 리스트를 출력합니다.

답변

실제로 8 바이트

;╗R`╜┤`░

온라인으로 사용해보십시오!

설명:

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

How IT

언제든지 물어보세요.

태그 보관물: primes

N까지 코 프리 1(함께 k출력 번호 중

답변

젤리 , 3 바이트

어떻게 작동합니까?

유효성 증명

답변

파이썬 2 , 61 47 바이트

배경

작동 원리

답변

젤리 , 4 바이트

작동 원리

답변

Mathematica, 25 바이트

답변

2sable , 4 바이트

답변

파이썬, 93 82 74 바이트

답변

실제로 8 바이트