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

다수 주어 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. 내재적으로 생성 된 범위 에는 및 됩니다. 최대 공약수는 항상 양의 정수이므로 은 항상 발생하며 항상 최소값이됩니다.

    [1,input]

    1

    1

    gcd(1,x)=1∀x∈Z∗

    1
  2. 두 개의 연속 양의 정수는 항상 coprime입니다. 고려 와 . 그런 다음 및 와 같은 또 다른 양의 정수 취 합니다. y = x + 1 k k x k y

    x,y∈Z∗

    y=x+1

    k

    k∣x

    k∣y

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

    k∣(y−x)

    k∣(x+1−x)

    k∣1

    1

    1

답변

파이썬 2 , 61 47 바이트

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

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

배경

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

(Zn,+n,⋅n)

n

Zn={0,…,n−1}

a n b = a b

a+nb=(a+b)%n

+ ,

a⋅nb=a⋅b%n

+,⋅, and %

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

a

b

Zn

n

1

a⋅nb=1%n

n > 1

1%n=1

n>1

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

n>1

a

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 Z

a⋅(x−y)%n=a⋅x%n−a⋅y%n=0

n∣a⋅(x−y)

n

a⋅(x−y)

n

a

n∣x−y

−n<x−y<n

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

x=y

a⋅n0,…,a⋅n(n−1)

Zn

Zn

n

1

b

a n b = 1

Zn

a⋅nb=1

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

n>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

. 반면에 이기 때문에 도 따릅니다 . 이 방법으로 이므로 가 소수 라는 가정과 모순 됩니다.

p∣n

p∣a⋅b−1

p∣(a⋅b)−(a⋅b−1)=1

p

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

n>1
  • N

    a

    와 은 coprime입니다.

    n
  • N

    a

    곱하기 역 모듈로 인정합니다 .

    n
  • N

    a

    고유 한 곱셈 역 모듈로 인정합니다 .

    n

작동 원리

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

a

b

Zn

k:=a⋅n+b

a

b

k

n

k

a=k/n

/N - 1 ≤의 N - 1 K Z의 N 2 유전율 ( N - 1 ) N + ( N - 1 ) = N (2) - 1

b=k%n

/

a≤n−1

b≤n−1

k

Zn2

k≤(n−1)⋅n+(n−1)=n2−1

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

a

n

b

k k / n = a k / n k

a⋅b%n=1

k

k/n=a

k/n⋅k%n=(k/n)⋅(k%n)%n=1

a

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

a

n

k a = k / n a

k/n⋅k%n=1

k

a=k/n

a

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

n

Zn

답변

젤리 , 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