В этом разделе мы изучим проверку числа на простоту, как можно найти все делители числа за $\sqrt{N}$ и разложение числа на простые числа
Что такое простое число?
Число называется простым тогда и только тогда, когда у ровно два делителя: и само число .
Как найти все делители числа ?
Наивное решение — пройтись по всем числам от до и проверить делимость.
Такой метод работает за . Как улучшить код?
Заметим: если число является делителем числа , то и число также является делителем , где .
Второе важное наблюдение: , то есть хотя бы один из делителей пары всегда не больше .
Это означает, что можно перебрать только числа от до . Если мы находим делитель , то добавляем также в множество делителей.
Таким образом, мы можем найти все делители числа за .
Пример кода:
Чтобы проверить число на простоту, достаточно посчитать количество его делителей.
Если количество делителей равно двум, то число является простым; в противном случае — составным.
Факторизация — это разложение числа на простые множители.
Алгоритм факторизации основывается на тех же идеях, что и проверка на простоту или поиск делителей, описанные выше.
Если у числа существует простой делитель, отличный от него самого, то он не превышает .
Для факторизации числа нужно перебирать все числа в диапазоне от до и последовательно делить на найденные делители.
for (int i = 1; i <= N; i++) {
if (N % i == 0) {
...
}
}
vector<int> divisors;
for (int a = 1; a * a <= N; a++) {
if (N % a == 0) {
int b = N / a;
divisors.push_back(a);
if (a != b) {
divisors.push_back(b);
}
}
}
vector<int> factors;
for (int i = 2; i * i <= N; i++) {
while (N % i == 0) {
factors.push_back(i);
N /= i;
}
}
if (N > 1) {
factors.push_back(N);
}