number-theory

Bo‘luvchilar — O(√n)

divs = []
i = 1
while i * i <= n:
    if n % i == 0:
        divs.append(i)
        if i != n // i:
            divs.append(n // i)
    i += 1

Tub sonlar — Eratosfen g‘alviri, O(n log log n)

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
        is_prime[i * i::i] = [False] * len(range(i * i, n + 1, i))

EKUB va EKUK

from math import gcd
lcm = a // gcd(a, b) * b         # avval bo‘lib, keyin ko‘paytiring — toshib ketmaydi

Modul bo‘yicha arifmetika

Javob «10⁹ + 7 ga bo‘lgandagi qoldiq» bo‘lsa, har qo‘shish va ko‘paytirishdan keyin % MOD qiling. Daraja: pow(a, n, MOD) — O(log n). Bo‘lish o‘rniga teskari element: pow(b, MOD - 2, MOD) (MOD tub bo‘lsa).