Факторизация числа за O(sqrt n): как разложить на простые и почему хватает корня?
Хочу разложить число n (до 10^12) на простые множители. Перебираю делители до n — это слишком долго. Почему достаточно перебирать до sqrt(n) и как правильно учесть оставшийся большой простой множитель? И где тут переполнение?
2 ответа
Достаточно перебирать делители до sqrt(n), потому что если n = a·b и оба a, b > sqrt(n), то a·b > n — противоречие. Значит хотя бы один делитель ≤ sqrt(n). Выделяя все такие множители, в конце мы либо получим 1, либо простое число, большее sqrt(n) (оно осталось одно).
vector<pair<long long,int>> factorize(long long n) {
vector<pair<long long,int>> f; // (простое, степень)
for (long long d = 2; d * d <= n; d++) { // важно: d*d, не d <= sqrt(n)
if (n % d == 0) {
int cnt = 0;
while (n % d == 0) { n /= d; cnt++; }
f.push_back({d, cnt});
}
}
if (n > 1) f.push_back({n, 1}); // оставшийся большой простой
return f;
}
Сложность — O(sqrt n). Грабли:
- Условие цикла пиши как
d * d <= n(а неd <= sqrt(n)—sqrtв double даёт погрешность). Так какn ≤ 10^12,d ≤ 10^6,d*d ≤ 10^12— вlong longвлезает, ноdиnобязаны бытьlong long. - Не забудь финальную проверку
if (n > 1)— это и есть последний крупный простой множитель, который перебор не достал.
Если чисел много и они до ~10^7, предподсчитай наименьший простой делитель lp[] линейным решетом — тогда каждая факторизация за O(log n) вместо O(sqrt n). Для очень больших одиночных чисел (до 10^18), где даже sqrt(n) = 10^9 не пролезает, нужен ро-алгоритм Полларда — он факторизует за ожидаемое O(n^{1/4}) с использованием теста Миллера-Рабина для проверки простоты. Но это уже тяжёлая артиллерия — на большинстве задач хватает O(sqrt n).