Basic Algorithms
Complexity Table
| Algorithm | Best | Average | Worst | Space | |-----------|------|---------|-------|-------| | Euclidean GCD | O(1) | O(log min(a,b)) | O(log min(a,b)) | O(1) | | Newton's cube root | O(1) | O(log 1/ε) | O(max_iter) | O(1) |
Euclidean GCD
Key identity: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a.
def gcd(a: int, b: int) -> int:
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
def lcm(a: int, b:
[Description truncada. Veja o README completo no GitHub.]