Math & Number Theory

Euclid's algorithm से GCD

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

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 होता है।

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 को अलग-अलग जांचने से कहीं तेज़।

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।