# Math & Number Theory — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/math-number-theory

> GCD, primality, और Sieve of Eratosthenes — interviews के लिए बार-बार आने वाला number-theory टूलकिट।

## Euclid's algorithm से GCD

`gcd(a, b) == gcd(b, a % b)`, अंत में `gcd(x, 0) == x` तक। LCM आता है `a * b / gcd(a, b)` से।

```python
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)
```

Output:

```
gcd(48, 18)  # 6
lcm(4, 6)    # 12
```

## Primality परीक्षण

Trial division को केवल `sqrt(n)` तक divisors जांचने की ज़रूरत है — square root से बड़े किसी भी factor का एक छोटा जोड़ीदार factor होता है।

```python
def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True
```

Output:

```
is_prime(97)   # True
is_prime(100)  # False
```

## Sieve of Eratosthenes

**n तक के सभी primes** खोजने के लिए, हर prime के गुणकों को `p*p` से शुरू करके composite चिह्नित करें। यह `O(n log log n)` में चलता है — हर number को अलग-अलग जांचने से कहीं तेज़।

```python
def sieve(n):
    is_composite = [False] * (n + 1)
    primes = []
    for p in range(2, n + 1):
        if not is_composite[p]:
            primes.append(p)
            for multiple in range(p * p, n + 1, p):
                is_composite[multiple] = True
    return primes
```

Output:

```
sieve(30)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```

## Modular arithmetic

बड़े परिणामों के लिए, हर multiplication/addition के बाद `% (10**9 + 7)` लगाएँ ताकि overflow न हो। याद रखें: `(a * b) % m == ((a % m) * (b % m)) % m`।