다수 주어 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]
우리는 또한 무한한 해결책이 있다고 확신하기 때문에 n
coprime 인 위의 숫자를 세지 않습니다 n
.
또한 참고 : 서로 공통된 숫자는 상대적으로 소수이거나 서로 소수입니다.
답변
젤리 , 3 바이트
gÐṂ
어떻게 작동합니까?
gÐṂ-(Monadic) 전체 프로그램. g-최대 공약수 ÐṂ-링크 값을 최소로 유지하십시오 (예 : GCD == 1 인 요소) 그러면 범위 [1, 입력] (포함)이 자동으로 생성됩니다.
유효성 증명
우리는 단지 coprimes을 추출 할 이후 가장 큰-공통 약수 목록의 최소값 이 될 1 에 대한 ÐṂ
트릭이 작동합니다. 이를 두 가지 방법으로 증명해 보자.
-
내재적으로 생성 된 범위 에는 및 됩니다. 최대 공약수는 항상 양의 정수이므로 은 항상 발생하며 항상 최소값이됩니다.
1
-
두 개의 연속 양의 정수는 항상 coprime입니다. 고려 와 . 그런 다음 및 와 같은 또 다른 양의 정수 취 합니다. y = x + 1 k k ∣ x k ∣ y
이것은 이므로 이므로 입니다. 을 나누는 유일한 양의 정수 는 자체이므로 목록에 표시되며 항상 최소값이됩니다.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 )
a ⋅ n b = a ⋅ b
+ ,
두 요소 및 의 상호라고 곱셈 역관계 모듈로 경우 . 참고 마다 .b Z n n a ⋅ n b = 1
1
n > 1
수정 및하자 의 서로 소가 될 에서 . 경우 개의 요소에 대한 및 의 , 우리가 그 . 이것은 의미가 , 우리는 다음과 즉, 균등하게 나눕니다 . 이후 과 공유 아무 주요 약수 이 그 의미 . 마지막으로a n Z n a ⋅ n x = a ⋅ n y x y Z n a ⋅ x
a ⋅ ( x − y )
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 ⋅ n b = 1
반대로, 수정 및하자 의 요소 수 되어 있지 에 서로 소 . 이 경우 및 과 같은 소수 있습니다. 경우 곱셈 역 모듈로 인정 (현실을 부르 자 , 우리가있는 것) , 의미가 , 따라서, 이므로 입니다. 이후 , 우리는 다음과a Z n n p p ∣ a p ∣ n a n b a ⋅ n b = 1 a ⋅ b
( a ⋅ b − 1 )
n ∣ a ⋅ b − 1 p ∣ a p ∣ a ⋅ b p ∣ n p ∣ a ⋅ b − 1 p ∣ ( a ⋅ b ) - ( a ⋅ b − 1 ) = 1 p
. 반면에 이기 때문에 도 따릅니다 . 이 방법으로 이므로 가 소수 라는 가정과 모순 됩니다.
이는 때 다음 명령문이 동일 함을 증명합니다 .
-
N
와 은 coprime입니다.
-
N
곱하기 역 모듈로 인정합니다 .
-
N
는 고유 한 곱셈 역 모듈로 인정합니다 .
작동 원리
정수의 각 쌍 및 에 , 정수 고유; 실제로 와 는 몫이고 나머지를 으로 나눈 값 , 즉 가 주어지면 및 복구 할 수 있습니다 . 여기서 정수 나누기를 나타냅니다 . 마지막으로 이고 이므로 는 의 요소입니다 . 실제로 입니다.b Z n k : = a ⋅ n + b a b k n k a = k / n b = k
/ ≤ N - 1 ㄱ ≤의 N - 1 K Z의 N 2 유전율 ≤ ( N - 1 ) ⋅ N + ( N - 1 ) = N (2) - 1
위에서 언급 한 바와 같이, 와 이 동일 프라임 인 경우 과 같은 고유 가있을 것입니다. 즉, 와 와 같은 고유 가있을 것입니다. , 이렇게 생성 된 목록에 포함 회만.n b a ⋅ b
k k / n = a k / n ⋅ k
반대로, 와 이 동일 프라임 이 아닌 경우 은 모든 값에 대해 과 같이 거짓 이므로 생성 된 목록에 포함 되지 않습니다. .n k / n ⋅ k
k a = k / n a
이것은 람다 리턴이 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