2021-11-09
44
3. Факторизация и подобное
Лемма Евклида
Если простое число p делит без остатка произведение двух целых чисел x * y, то p делит x или y.
Любое натуральное число, отличное от 1, единственным образом (с точностью до порядка сомножителей, принято записывать простые множители в порядке возрастания) можно представить в виде произведения простых множителей.
Любое число можно проверить на простоту за корень, так как самый маленький делитель не превышает корня из числа. Также за корень можно выполнить факторизацию или поиск всех делителей числа.
| vector<pair<int, int > > factorization(int a) { vector<pair<int, int > > rs; int orig = a; // или перебирать до константы for (int i = 2; i * i <= orig; ++i) { if (a % i == 0) { rs.push_back(make_pair(i, 1)); a /= i; while (a % i == 0) { a /= i; ++rs.back().second; } } } if (a!= 1) rs.push_back(make_pair(a, 1)); return rs; } vector<int> all_divisors(int a) { vector<int> rs; for (int i = 2; i * i <= a; ++i) {// или перебирать до константы if (a % i == 0) { rs.push_back(i); int i2 = a / i; if (i2 <= i) break; rs.push_back(i2); } } sort(rs.begin(), rs.end()); } bool isPrime(int x) { for (int i = 2; i * i <= x; ++i) { if (x % i == 0) return 0; } return 1; } |
Если у нас уже найдены все простые числа, то факторизацию можно проводить перебирая только простые.
По факторизации можно найти количество всех делителей - очевидно, что каждое простое в факторизации может входить в делитель со степенью от 0 до степени вхождения в факторизацию.
Количество делителей числа порядка кубического корня.
Если n <=10**9, то количество делителей <= 1500
Если n <=10**18, то количество делителей <= 105000
Количество простых делителей числа не превосходит логарифма
