Estou resolvendo [este problema do URI][1] que pede, basicamente, que se encontre o máximo divisor comum entre dois valores.
Resolvi originalmente com o math.gcd
em meia dúzia de linhas, porém, o código não foi aceito já que o URI utiliza uma versão do Python 3 anterior à inclusão do gcd
. Pois bem, assim resolvi o problema de uma outra maneira:
N = int(input())
monte, maior = [], 0
for x in range(N):
A, B = input().split(' ')
A, B = int(A), int(B)
for x in range(A, 1, -1):
if A % x == 0:
monte.append(x)
for x in range(len(monte)):
if B % monte[x] == 0:
maior = monte[x]
break
print(maior)
As saídas estão todas corretas, mas problema é que meu código está sendo recusado por exceder o tempo limite.
Pergunto: Como posso melhorar o mesmo? Já enxuguei tudo o que consegui, mas continua excedendo o tempo limite. Alguma sugestão? [1]: https://www.urionlinejudge.com.br/judge/pt/problems/view/1028