Как найти все факторы данного числа N с временной сложностью меньше, чем N?

Question

Как найти все факторы данного числа N с временной сложностью меньше, чем N?

я пытаюсь это, но на входе> 10000 этот идентификатор цикла занимает гораздо больше времени.

Есть ли способ оптимизировать это, который имеет сложность времени меньше, чем N или (logn)?

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
int n = 10001;

for (int i = 1; i < n; i++) {
if (n % i == 0) {
cout << i;
}
}
return 0;
}

0

c++factors

Решение

Другие решения

Вы можете перебирать только квадратный корень из n, а не n, поскольку все, что больше квадратного корня, не может быть фактором n. редактировать: читать ComicSansMs ответ был лучше, чем мой редактировать

1

Первый шаг — найти все основные факторы с их множественностью. Тогда вы можете легко генерировать факторы.

Найти основные факторы довольно быстро в среднем для чисел до 100000000, если вы делаете это разумно. Если вы найдете фактор, вы можете разделить его на n, что значительно сокращает время в общем случае. Также вам нужно только проверить нечетные коэффициенты до sqrt (n), кроме 2:

// I assume n is non-zero
while (!(n & 1)) {
cout << "2" << endl;
n /= 2;
}
for (unsigned int factor = 3; factor * factor <= n; factor += 2) {
while (n % factor == 0) {
cout << factor << endl;
n /= factor;
}
if (n != 1)
cout << n << endl;
}

1

Если вам нужно выполнить это много раз, есть хорошее решение. Я приведу только пример, реализация будет вашим бизнесом.

Допустим, вам нужно разложить два числа, например 580 и 72.

Сначала вы разложите его на простые числа

580 = 2 x 2 x 5 x 29
72 = 2 x 2 x 2 x 3 x 3

Скорость разложения на простые числа может быть значительно увеличена с помощью кэширования. У тебя должно быть std::set<int> который содержит все известные простые числа, поэтому после разложения 580 это содержит 2, 5, 29, Это значит факторизовать 72 вам нужно только определить, что 3 прост.

После того, как у вас есть все основные факторы, вам нужно умножить их во всех комбинациях, чтобы получить не простые факторы.

Как я уже говорил, это решение действительно хорошо только в том случае, если вам нужно разложить много чисел, но если вам нужно разложить только один раз, это просто неплохо. просеивание было бы лучше.

0

Источник

Accepted Answer

В дополнение к dmh2000 ответ: Вы можете использовать избыточность в проверке. Например, если число не делится на n это также не делится на любой кратный n, Например, число, которое не делится на 2, также нельзя разделить на 4, 6 или 8.

Этот метод известен как просеивание.

2