fork download 
  1. def gcd2(m, n):
  2.     factor = 1
  3.  
  4.     while m > 1 and n > 1:
  5.  
  6.         if m % 2 == 0 and n % 2 == 0:
  7.             factor *= 2
  8.             m /= 2
  9.             n /= 2
  10.             continue
  11.         elif m % 2 != 0 and n % 2 != 0:
  12.             m, n = abs(m - n) / 2, min(m, n)
  13.             continue
  14.  
  15.         if m % 2 == 0:
  16.             m /= 2
  17.  
  18.         if n % 2 == 0:
  19.             n /= 2
  20.  
  21.     if m == 0 or n == 0:
  22.         out = m + n
  23.     elif n == m:
  24.         out = n
  25.     elif m == 1 or n == 1:
  26.         out = 1
  27.  
  28.     return factor * out
  29.  
  30.  
  31. def gcd(m, n):
  32.     if m == 0:
  33.         return n
  34.  
  35.     if n == 0:
  36.         return m
  37.  
  38.     if m == n:
  39.         return n
  40.  
  41.     if m == 1 or n == 1:
  42.         return 1
  43.  
  44.     if m % 2 == 0 and n % 2 == 0:
  45.         return 2 * gcd(m / 2, n / 2)
  46.  
  47.     if m % 2 == 0 and n % 2 != 0:
  48.         return gcd(m / 2, n)
  49.  
  50.     if n % 2 == 0 and m % 2 != 0:
  51.         return gcd(m, n / 2)
  52.  
  53.     if m % 2 != 0 and n % 2 != 0:
  54.         if n > m:
  55.             return gcd((n-m)/2, m)
  56.  
  57.         else:
  58.             return gcd((m-n)/2, n)
  59.  
  60. import random
  61. import timeit
  62.  
  63. for test in range(100):
  64.     a, b = random.randint(0, 100), random.randint(0, 100)
  65.     fa = gcd(a, b)
  66.     fb = gcd2(a, b)
  67.     assert fa == fb, 'Not ok'
  68.  
  69. # number = 10 ** 5
  70. # print timeit.timeit('gcd(a, b)', setup=s, number=number)
  71. # print timeit.timeit('gcd2(a, b)', setup=s, number=number)
  72. print 'ok'
  73.  
Success #stdin #stdout 0.12s 11072KB
comments (?)
stdin 
Standard input is empty
stdout 
ok
https://ideone.com/ya1Q9L
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!