Как найти количество делителей числа.
Например число
20 -> 1 2 4 5 10 20
1 -> 1 = 1
2 -> 1, 2 = 2
4 -> 1, 2, 4 = 3
5 -> 1, 2 = 2
10 -> 1, 2, 5, 10 = 4
20 -> 1, 2, 4, 5, 10, 10 = 6
1 + 2 + 3 + 2 + 4 + 6 = 18
Asked
Active
Viewed 1.3k times
2
Stanislav Volodarskiy
- 33,556
RockyB
- 29
3 Answers
5
Откровенно говоря, ничего умнее, чем перебор простых делителей числа до sqrt(N) не вижу. Ну, а потом - перебор сочетаний этих простых делителей в составные делители. Понятно, что при нахождении простого делителя делим число на него и начинаем все сначала. И не менее понятно, что количество всех сочетаний (== количество делителей) есть просто произведение всех степеней простых делителей, увеличенные на 1. Ну, например, 360 = 2^3 * 3^2 * 5^1, так что число делителей (3+1)*(2+1)*(1+1)=24.
Если числа небольшие - можно просто перебор всех подряд делителей до sqrt(N), с учетом, что для каждого такого делителя, отличного от 1, есть соответствующий делитель с обратной стороны от sqrt(N).
Код нужен? :)
Update: пример - вывод количества всех делителей (включая 1 и само число)
Harry
- 221,325
-
1Ну если совсем все плохо, то можно массив простых чисел в константы записать, чтобы не все до корня проверять. А можно в сторону вероятностных тестов попробовать посмотреть http://e-maxx.ru/algo/factorization – pavel Sep 03 '16 at 07:26
-
@pavel Так вы получите только разложение на более мелкие числа. И к каждому все равно надо делать свой вариант... – Harry Sep 03 '16 at 07:27
-
Если это сделать быстро, то дальше ещё быстрее будет. Если числа ну очень большие а делителей немного то эффект будет. – pavel Sep 03 '16 at 07:29
-
@pavel А потом их компоновать... По-моему, на простые делители - лучше всего, после этого количество делителей - просто произведение увеличенных на 1 степеней (минус 1, если не считать само число). Простые числа теоретически линейным решетом Эратосфена дают
O(sqrt(N)), но вот дальше что-то у меня оценка не получается. Но никак не хужеO(sqrt(N)*lg N), нет? тогда выходитO(N*lg N)- что-то в таком духе? – Harry Sep 03 '16 at 07:33 -
Да, на простые конечно удобнее всего, просто если числа большие (например в криптографии полезли) то до корня это слишком долго, поэтому есть специфические методы которые порядка log^2 работают. В предыдущем комментарии я имел ввиду что хоть как-то разделить число уже полезно, т.к. мы переходим к той же задаче но с меньшим размером. Конечная цель - факторизация. – pavel Sep 03 '16 at 07:37
-
1@pavel А, теперь понял вашу мысль, да, конечно. Но если ограничиваться обычными 32-битными типами, то перебор вполне пойдет... – Harry Sep 03 '16 at 07:41
-
Кстати у вас чуть ошибка, для 1 как раз есть обратный элемет- само число, а вот для точного корня обратного нет. – pavel Sep 03 '16 at 07:43
-
@pavel Ну, в исходном вопросе мне показалось, что само число как делитель не рассматривается. Ну а корень - понятно, что обратный такой же, так что... :) Вобщем, код я набросал, если где ошибка - допускаю, что может быть, писал на бегу, что называется, проверял только на 3-5 числах... – Harry Sep 03 '16 at 07:54
-
1Найдя один делитель, можно разделить на него, и искать дальше от текущего делителя до корня из нового, меньшего числа. – VladD Sep 03 '16 at 08:06
-
@VladD Мда... а ведь и в самом деле, кому-то это может показаться не очевидным. Понятно, что в коде я именно так и поступал. Но при переборе ВСЕХ делителей (включая составные) это как раз делать не нужно. – Harry Sep 03 '16 at 08:09
-
1Вообще для этой задачи лучше бы подошла модифиция решета, в которой вместо флага простоты хранится один из делителей числа(обычно наименьший, можно наибольший). Сложность построения та же – pavel Sep 03 '16 at 08:15
-
@Harry: Ну, быстрее будет перебрать все простые делители. Если разложение на простые множители имеет вид
p1^k1 * ... * pn^kn, то количество всех делителей, очевидно, равно(k1 + 1) * ... * (kn + 1). – VladD Sep 03 '16 at 08:19 -
@VladD Что-то из меня хреновый писатель сегодня. Я пишу, казалось бы, то же самое, но получается не так :) В коде я именно так и поступаю. – Harry Sep 03 '16 at 08:28
-
0
Можно, найти алгоритм и немного получше, чем перебор простых делителей числа до sqrt(N).
Обратим внимание на тот факт, что любое число, можно представить как произведение простых множителей, таким образом если мы нашли один простой делитель, то далее нам не надо искать делители N, а надо искать делители от частного N/x, где х - наш простой делитель.
Например так. (Извиняюсь за C#)
uint[] simpl_arr = //массив заполненный простыми числами
public List<int> GetSimpleDividors(uint number)
{
List<int> result = new List<int>();
uint s = Convert.ToUInt32(Math.Ceiling(Math.Sqrt(number)));
for ( int i = 0 ; simple_arr[i] < s ; i++ )
{
if (number % simple_arr[i] == 0)
{
result.Add(simple_arr[i]);
uint quotient = number / simple_arr[i];
var tmp = GetSimpleDividors(quotent);
if (tmp.Count > 0)
{
result.AddRange(tmp);
}
else
{
result.Add(quotent);
}
break;
}
}
return result;
}
Mirdin
- 5,849
-
А можно код с рекурсией? Я честно не представляю как она делает код лучше. – pavel Sep 03 '16 at 12:36
-
@pavel, я плюсы почти не помню... :), но здесь напрашивается явно - находим первый делитель, и вызываем ее же для частного. – Mirdin Sep 03 '16 at 12:51
-
лёгким движением руки сложность из очевидного корня становится что-то порядка n^(5/6) – pavel Sep 03 '16 at 13:43
-
0
Можно в цикле через алгоритм Евклида считать до деления на 0.
До конца цикла проверять результат деления: если остаток от деления равен 0, то прибавить 1 к счётчику.
В счётчике считаем количество делителей.
Xalion
- 36
if(n℅i==0) cout << i;где n - ваше число. Вывод можно организовать в какой нибудь вектор. – Nik Sep 03 '16 at 06:16