"0811 coprime test"의 두 판 사이의 차이
ph
(새 문서: <pre> #coprime test def gcd(a,b): [n, m] = sorted([a,b]) q = m%n if q ==0: return n else: return gcd(n, q) def iscoprime(a,b): return gcd(a,b) ==...) |
잔글 |
||
| (같은 사용자의 중간 판 10개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
<pre> | <pre> | ||
#coprime test | #coprime test | ||
| − | def gcd( | + | def gcd(m,n): |
| − | + | while m%n != 0: | |
| − | + | m, n = n, m%n | |
| − | + | return n | |
| − | |||
| − | |||
| − | |||
def iscoprime(a,b): | def iscoprime(a,b): | ||
return gcd(a,b) == 1 | return gcd(a,b) == 1 | ||
</pre> | </pre> | ||
| + | |||
| + | precisely, | ||
| + | <pre> | ||
| + | def iscoprime(m,n): # m>n test is not required. | ||
| + | while m%n != 0: | ||
| + | m, n = n, m%n | ||
| + | return n==1 | ||
| + | </pre> | ||
| + | is가 아니고 are인가... | ||
| + | |||
| + | <disqus/> | ||
2017년 9월 3일 (일) 17:17 기준 최신판
#coprime test
def gcd(m,n):
while m%n != 0:
m, n = n, m%n
return n
def iscoprime(a,b):
return gcd(a,b) == 1
precisely,
def iscoprime(m,n): # m>n test is not required.
while m%n != 0:
m, n = n, m%n
return n==1
is가 아니고 are인가...