he-013

# HumanEval/13

Implement a file **`solution.py`** that completes the function below. Keep the given name and signature; your file must define it at module level.

```python


def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
```

<!-- imported from OpenAI HumanEval (HumanEval/13) -->

# Auto-generated from OpenAI HumanEval HumanEval/13. Do not edit by hand.
from solution import *  # noqa: F401,F403 (prompt helpers may be referenced by tests)
from solution import greatest_common_divisor as candidate

METADATA = {
    'author': 'jt',
    'dataset': 'test'
}


def check(candidate):
    assert candidate(3, 7) == 1
    assert candidate(10, 15) == 5
    assert candidate(49, 14) == 7
    assert candidate(144, 60) == 12


def test_he_013():
    check(candidate)

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

The user wants me to implement a function `greatest_common_divisor(a: int, b: int) -> int` that computes the greatest common divisor (GCD) of two integers.

I can use the Euclidean algorithm to compute the GCD.
Python's `math` module has `math.gcd`, but I should probably implement it manually or just use `math.gcd`. The problem statement doesn't forbid using `math.gcd`, but implementing it manually is straightforward.

Let's implement the Euclidean algorithm:
```python
def greatest_common_divisor(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

Wait, the problem says "greatest common divisor of two integers a and b". Usually, GCD is positive. The Euclidean algorithm handles negatives if we take absolute values, or Python's `%` operator handles negatives correctly for GCD purposes, but taking absolute values is safer.

Let's check the examples:
`greatest_common_divisor(3, 5)` -> 1
`greatest_common_divisor(25, 15)` -> 5

The implementation is straightforward.

I will write the complete function in `solution.py`.

```python
def greatest_common_divisor(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

Wait, should I handle the case where both are 0? GCD(0, 0) is typically 0. The loop handles it: `a=0, b=0` -> returns 0. That's fine.

Let's double check the exact signature and docstring.
```python
def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

This matches the requirement. I'll output it as requested.
No extra fluff.
I'll wrap it in a code block.
Done. 
Let's verify one more time.
Euclidean algorithm is correct.
Type hints match.
Docstring matches.
Ready. 
Output matches request.
Proceeds. 
Self-Correction/Verification during thought: 
Could also just use `import math; return math.gcd(a, b)`. But manual implementation is fine and often preferred in these coding challenges to avoid imports if not necessary, though imports are usually allowed. I'll stick to the manual implementation as it's robust.
The problem is from HumanEval/13. The standard solution often uses `math.gcd` or Euclidean algorithm. Both are fine.
I will provide the manual implementation.
All good. 
Output matches. 
Proceeds. 
```python
def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```
This is correct.
Done. 
Output generation. 
[Done]