По основной теореме арифметики любое натуральное число, кроме \(1\), можно представить как произведение простых чисел.
Давайте сначала докажем, что количество простых чисел бесконечно. Пускай мы имеем конечный набор из \(k\) простых чисел \(p_1, p_2 ... p_k\).
Рассмотрим \(S = p_1 \cdot p_2 ... \cdot p_k + 1\). Существует два варианта. Первый - \(S\) простое, не входящее в наш набор. Второй - число составное. Тогда существует простое число \(x\), которое не входит в набор (т.к. все числа из набора делят \(S\) с остатком 1), но делит \(S\). Таким образом, всегда можно найти еще одно простое число, не входящее в конечный набор.
Оценим количество делителей у числа. Чтобы перебрать все делители \(x\) достаточно перебрать все числа до \( \sqrt{x}\). То есть верхняя оценка количества делителей - квадратный корень.
Более того, опытным путем можно увидеть что максимальное число делителей у первых \(n\) чисел порядка \( \sqrt[3]{n}\).
Гипотеза Гольдбаха: любое четное натуральное число можно разложить на сумму двух простых (доказано эмпирически для чисел до \(10^{18}\)).
Если взять любое простое число и вычитать из него наибольшее простое, меньшее самого числа, то потребуется не более \(4\)-х итераций (доказано эмпирически).
Пусть даны два числа - \(a\) и \(b\). Необходимо найти \(НОД(a,b)\). Будем рекурсивно поддерживать \(a\) и \(b\).
Если \(a\) делит \(b\) нацело или наоборот, выходим из алгоритма, возвращая делитель. Пускай \(a > b\) (в противном случае просто поменяем их местами). Тогда сделаем \(a' = a - b\) и запустим алгоритм с новыми параметрами.
Очевидно, что при большом \(a\) и маленьком \(b\) алгоритм будет выполняться долго. Не менее очевидно, что из \(a\) можно вычесть \(b\) ровно \( \lfloor \frac{a}{b} \rfloor \) раз.
Тогда модифицируем наш алгоритм: вместо вычитания будем применять остаток от деления. Код алгоритма будет примерно таким:
int gcd(int a,int b)
{
if(a < b )
swap(a, b);
while( a%b ) {
a %= b;
swap(a, b);
}
return b;
}
Работает он порядка \( \log{x} \) операций (худший случай - мы будем просто вычитать одно число каждый раз, то есть будет последовательность вида чисел Фибоначчи, которые растут с экспоненциальной скоростью).
Из-за того, что операция деления очень медленная, очевидно что он будет работать не так уж и быстро как бы хотелось.
Эту проблему решает бинарный алгоритм Евклида.
Он заключается в трех фактах, следовательно три случая:
В приоритете первые два варианта, т.к. они уменьшают числа в два раза. В противном случае, они оба нечетны. Мы вычтем из одного нечетного другое нечетное, и получится одно четное и второе нечетное. То есть мы не можем больше одной операции вычитать подряд. Следовательно асимптотика также \(O(\log{n})\), только быстрее.
Заметим, что мы сначала вынесем за скобки степень \(2\) и больше этого делать не будем.
int bgcd(int a,int b)
{
if(a==0) return b;
if(b==0) return a;
int az=__builtin_ctz(a);//макс.степень 2 в a
int bz=__builtin_ctz(b);//макс.степень 2 в b
int v = min(az,bz);//выносим за скобки макс.степень
b >>= bz;//сокращаем сначала b
while(a) { // нод(0,b) = b
a >>= az;
int d = b-a;
az =__builtin_ctz(d);
// <== пересчитываем макс.степень для второго случая
b = min(a,b);
a = abs(d);
}
return b << v;
//домножаем на степень, которую выносили
}
Таким образом, такой алгоритм работает гораздо быстрее. Код конкретно этой реализации был взят отсюда
Решето Эратосфена работает по следущему принципу: выпишем все числа от \(2\) до \(n\). Возьмем \(2\) как самое первое число. \(2\) - простое число. Вычеркнем все числа, которые делятся на \(2\). Возьмем \(3\), как самое первое нерассмотренное число. \(3\) - простое число. Вычеркнем все невычеркнутые числа кратные \(3\). \(4\) вычеркнуто, его не рассматриваем. \(5\) не вычеркнуто, вычеркнем все числа кратные 5...
Все невычеркнутые числа - простые. Рассмотрим реализацию
vector< int > primeNums;
bool isPrime[n+1]; // если x простое - isPrime[x] = 1, иначе - 0
memset(isPrime,1,n+1);
isPrime[0]=isPrime[1]=0;
for(int i = 0;i <= n;i++)
if(isPrime){
primeNums.push_back(i);
for(int j = i*i; j <= n;j+=i) // перебираем все кратные i
isPrime[j] = 0;
}
Время работы решета близка к линейной, что позволяет использовать его в большом количестве задач.
Если использовать битсеты вместо массива, решето ускоряется еще сильнее.
Кроме того, его можно модифицировать, чтобы вычислять самые разные величины (например, вычислять количество делителей или функцию Эйлера и факторизовывать числа).
Нам требуется не более \(\sqrt{n}\), чтобы факторизовать число, т.к. не более одного простого делителя больше корня числа.
Итого - асимптотика \(O(\sqrt{n})\). Можно улучшить предподсчитав все простые. Тогда мы улучшим ее до \(O( \frac{ \sqrt{n} }{ \log{\sqrt{n}}} ) \)
vector< int > primeNums;
// ... Предподсчет простых чисел
vector< pair< int,int > > divs; // пара p^w
for(int i=0; primeNums[i]*primeNums[i] <= n; i++)
if(n % primeNums[i] == 0)
{
int power = 0;
while(n % primeNums[i] == 0)
n/=primeNums[i], power++;
divs.emplace_back(primeNums[i], power);
}
if(n!=1) divs.emplace_back(n, 1);
Алгоритм позволяет за секунду разложить числа вплоть до \(10^{17}\), если предподсчитаны все его простые делители.
Если есть возможность предподсчитать решето Эратосфена до \(n\), то можно факторизовывать числа за \(\log{n}\) - для каждого числа запишем его делитель (когда будем проходить вторым циклом и помечать все числа, что делятся на это простое). Запишем это простое, поделим на него и снова запустим цикл, пока число не станет простым. Любое простое число \(2 \le\), значит в худшем случае \(\log{n}\) операций.