Переполнение при разложении на простые множители
vector<int> fact;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
fact.push_back(i);
while (n % i == 0)
n /= i;
}
if (n > 1)
fact.push_back(n);
Вот алгоритм разложения числа на простые множители. Может ли тут быть переполнение в i*i? И как его избежать, если да?
Ответы (2 шт):
Автор решения: Harry
→ Ссылка
Во-первых, лучше использовать unsigned int, во-вторых - да, может - если у вас n - тоже unsigned int и представляет собой простое число, большее 4294836225 (говорю о 32-битных числах).
Можно избежать переполнения путем дополнительной проверки, что i <= 0xFFFF.
Если n имеет тип int, то выбор для i типа unsigned int решает проблему - переполнения не будет.
И можно уменьшить число проверок в 2 раза, если вынести проверку для 2 отдельно, а потом проверять
for (int i=3; i*i<=n; i+=2)
Автор решения: MBo
→ Ссылка
Если предполагается, что n сможет быть велико, проще будет один раз вычислить sqrt(n) и сравнивать i с ним