Решето Эратосфена. Бинарное возведение в степень

7. Решето Эратосфена

Решето Эратосфена — это алгоритм, позволяющий найти все простые числа в отрезке [1; n] за O (n log log n) операций.

Идея проста — запишем ряд чисел 1... n, и будем вычеркивать сначала все числа, делящиеся на 2, кроме самого числа 2, затем делящиеся на 3, кроме самого числа 3, затем на 5, затем на 7, 11, и все остальные простые до n.

vector<int> init_prime(int cnt = 20000100) { vector<char> isPrime(cnt, 1); vector<int> prime; isPrime[0] = isPrime[1] = 0; for (int i = 2; i < cnt; ++i) { if (isPrime[i]) { if (1LL * i * i < cnt) { for (int j = i * i; j < cnt; j += i) isPrime[j] = 0; } prime.push_back(i); } } return prime; }

Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем O(n log n): даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту (собственно, так алгоритм тоже крайне часто используется, например чтобы для большого количества чисел подсчитать сумму всех делителей) (доказывается формулой суммы гармонического ряда).

Итоговую асимптотику в O (log log n) доказывать не будем.

8. Бинарное возведение в степень

Для того, чтобы быстро возвести число в большую степень можно воспользоваться следующей закономерностью:

x^n = (x^(n / 2))^2, if n % 2 == 0

x * x^(n - 1), if n % 2!= 0

на основании данного рекуррентного соотношения можно написать следующий код:

int binpow(int a, int n) { if (n == 0) return 1; if (n % 2 == 1) return binpow(a, n - 1) * a; else { int b = binpow(a, n / 2); return b * b; } } int binpowspeed(int a, int n) { if (!n) return 1; if (n & 1) return binpow(a, n - 1) * a; int b = binpow(a, n >> 1); return b * b; } int binpowmod(int a, int n, int mod) { if (!n) return 1; if (n & 1) return (((long long)binpowmod(a, n - 1, mod)) * a) % mod; int b = binpowmod(a, n >> 1, mod); return (long long)b * b % mod; } int binpownorec(int a, int n) { int res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; }

Заметим, что вычислять степень можно и по модулю, однако о модулярных вычислениях поговорим позднее.

Бинарное возведение в степень можно превратить в бинарное умножение, обычно используется когда нужно перемножить большие числа по большому модулю. Достаточно вспомнить, что умножение это повторение прибавлений.

a * b = a * 2 * (b / 2), if b % 2 == 0

= a + a * (b - 1), if b % 2!= 0

int binmult(int a, int b) { if (b == 0) return 0; if (b % 2 == 1) return binmult(a, n - 1) + a; else { int b = binmult(a, b / 2); return b * 2; } }