# Перебор всех делителей числа
1. **Наивный алгоритм за $O(n)$**

vector<int> divisors;
for(int i = 1; i <= n; i++){
    if(n % i == 0)
        divisors.push_back(i);
}

2. **Улучшенный алгоритм за $O(\sqrt{n})$**
Заметим факт, что если $\frac{n}{a} = b$ и $a < \sqrt{n}$, то $b > \sqrt{n}$ ($a$ и $b$ - целые числа).
Следовательно нам достаточно перебрать делители до $\sqrt{n}$.

vector<int> divisors;
for(int i = 1; i <= sqrt(n); i++){
    if(n % i == 0){
        divisors.push_back(i);
        if(i != n / i)
            divisors.push_back(n / i);
    }
}

3. **Проверка на простоту**
Число $n$ является **простым**, если оно не имеет делителей, кроме $n$ и $1$.

bool isPrime(int n){
    if(n == 1)
        return false;
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

# Решето Эратосфена
**Решето Эратосфена** позволяет найти все простые числа в на отрезка за $O(n\log{\log{n}})$

int n;
bool notPrime[n + 1];
// ввод
fill(notPrime, notPrime + n + 1, 0);
notPrime[0] = notPrime[1] = true;

vector<int> primes;

for(long long i = 2;i <= n;i++){
    if(notPrime[i])
        continue;
    primes.push_back(i);
    if(i * i >= n)
        continue;
    for(int j = i * i; j <= n; j += i)
        notPrime[j] = true;
}

# Быстрое возведение в степень
1. **Наивное решение за $O(p)$**

int x, p;
//ввод
int ans = 1;
for(int i = 0;i < p;i++)
    ans *= x;

2. **Улучшенный алгоритм за $O(\log{p})$**
Заметим, что для любого **чётного** $p$ выполняется свойство:
$x^p = x^{\frac{p}{2}} * x^{\frac{p}{2}}$
А для **любого** $p$ выполняется:
$x^p = x^{p - 1} * x$
Значит мы можем переписать алгоритм таким образом:

int binPow(int x, int p){
    if(p == 0)
        return 1;
    if(p % 2 == 1)
        return binPow(x, p - 1) * x;
    int X = binPow(x, p / 2);
    return X * X;
}

В худшем случае функия будет вызвана $2 *\log{n}$ раз.
Также данный алгоритм называют **бинарным возведением в степень**.

Реализация возведения $x$ в степень $p$ по **модулю** $m$.

ll binPow(int x, int p, ll m){
    if(p == 0)
        return 1;
    if(p % 2 == 1)
        return (binPow(x, p - 1) * x) % m;
    int X = binPow(x, p / 2);
    return (X * X) % m;
}

3. Итеративная реализация

int binPow(int x, int p){
   int now = 1;
   while(p != 0){
       if(p % 2 == 1){
           now *= x;
           p--;
       }
       x *= x;
       p /= 2;
   }
   return now;
}

Реализция с **модулем**

ll binPow(ll x, ll p, ll m){
   ll now = 1;
   while(p != 0){
       if(p % 2 == 1){
           now = (x * now) % m;
           p--;
       }
       x = (x * x) % m;
       p /= 2;
   }
   return now;
}

# НОД
**НОД** - Наибольший Общий делитель.
То есть, НОД($a$, $b$) = $max(k)$ такое, что $k$ делит и $a$, и $b$.
Алгоритм поиска НОДа:

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

Этот алгоритм называется - **Алгоритм Евклида**
Время работы $O(\log{n})$
**Доказательство:**
1. Пусть $k$ — любой общий делитель чисел $a$ и $b$, тогда $a=t1*k$, $b=t2*k$.
2. Тогда $k$ также общий делитель чисел $b$ и $r$, так как $b$ делится на $k$, а $r=a−b*q=(t1−t2*q)*k$
3. Обратное также верно и доказывается аналогично.
4. Следовательно, все общие делители пар чисел $a$, $b$ и $b$, $r$ совпадают. Другими словами, нет общего делителя у чисел $a$, $b$, который не был бы также делителем $b$, $r$, и наоборот.
# НОК
**НОК** - Наибольшее Общее кратное
То есть, НОК($a$, $b$) = $min(k)$ такое, что $k$ делится и на $a$, и на $b$.

Как же его найти? Довольно просто НОК($a$, $b$) = $\frac{a * b}{gcd(a, b)}$