0811 coprime test: 두 판 사이의 차이
ph
잔글편집 요약 없음 |
잔글편집 요약 없음 |
||
| 10번째 줄: | 10번째 줄: | ||
def iscoprime(a,b): | def iscoprime(a,b): | ||
return gcd(a,b) == 1 | return gcd(a,b) == 1 | ||
</pre> | |||
without recursion, | |||
<pre> | |||
def gcd(m,n): | |||
#[n, m] = sorted([a,b]) | |||
while m%n != 0: | |||
m, n = n, m-n*(m/n) | |||
return n | |||
</pre> | </pre> | ||
2017년 8월 11일 (금) 16:12 판
#coprime test
def gcd(m,n):
q = m%n
if q ==0:
return n
else:
return gcd(n, q)
def iscoprime(a,b):
return gcd(a,b) == 1
without recursion,
def gcd(m,n):
#[n, m] = sorted([a,b])
while m%n != 0:
m, n = n, m-n*(m/n)
return n