Быстрое нахождение количества делителей натурального числа

@Thinker · Регистрация: 26.08.2011

Студворк — интернет-сервис помощи студентам

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// быстрый алгоритм без использования дополнительной памяти
unsigned long Count(unsigned long a)
{
   unsigned long count = 1, k = 0, i;
   if (a == 1 || a == 2)
      return a;
   while ((a & 1) == 0)
   {
      k++;
      a >>= 1;
   }
   if (a == 1)
      return k + 1;
   else
      count = k + 1;
   for(i = 3; i*i <= a; i += 2)
   {
      k = 0;
      while(a % i == 0)
      {
         k++;
         a /= i;
      }
      count *= (k + 1);
   }
   if (a > 1)
      count <<= 1;
   return count;
}

Если имеется возможность выделения дополнительной памяти, то можно ускорить предыдущий алгоритм за счет введения массива простых чисел. В алгоритме ниже размер массива prime не зависит от функции Count (и наоборот), поэтому данный массив можно расширить. Чем больше в нем элементов при большом тестируемом числе, тем лучше

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// быстрый алгоритм с использованием дополнительной памяти
#define N 100
 
unsigned long prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541};
 
unsigned long Count(unsigned long a)
{
   unsigned long count1 = 1, count2 = 1, k, i;
   if (a == 1 || a == 2)
      return a;
   for(i = 0; i < N && prime[i]*prime[i] <= a; i++)
   {
      k = 0;
      while(a % prime[i] == 0)
      {
         k++;
         a /= prime[i];
      }
      count1 *= (k + 1);
   }
   if (a == 1)
      return count1;
   if (i < N)
      return count1 << 1;
 
   for(i = prime[N - 1] + 2; i*i <= a; i += 2)
   {
      k = 0;
      while(a % i == 0)
      {
         k++;
         a /= i;
      }
      count2 *= (k + 1);
   }
   if (a > 1)
      count2 <<= 1;
   return count1 * count2;
}

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define N 100
 
unsigned long prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541};
 
unsigned long Count(unsigned long a)
{
   unsigned long count1 = 1, count2 = 1, k = 0, i;
   if (a == 1 || a == 2)
      return a;
   while ((a & 1) == 0)
   {
      k++;
      a >>= 1;
   }
   if (a == 1)
      return k + 1;
   else
      count1 = k + 1;
   for(i = 0; i < N && prime[i]*prime[i] <= a; i++)
   {
      k = 0;
      while(a % prime[i] == 0)
      {
         k++;
         a /= prime[i];
      }
      count1 *= (k + 1);
   }
   if (a == 1)
      return count1;
   if (i < N)
      return count1 << 1;
 
   for(i = prime[N - 1] + 2; i*i <= a; i += 2)
   {
      k = 0;
      while(a % i == 0)
      {
         k++;
         a /= i;
      }
      count2 *= (k + 1);
   }
   if (a > 1)
      count2 <<= 1;
   return count1 * count2;
}

Предлагаю всем желающим попробовать свои силы и написать что-то быстрее представленного выше.

@yekka · 28.09.2012, 21:58

Сообщение от Thinker

#define N 100

N -- это количество простых чисел в нижеследующем массиве что ли?

@Thinker · 28.09.2012, 22:12 **[ТС]**

Сообщение от yekka

N -- это количество простых чисел в нижеследующем массиве что ли?

да, именно. массив можно и из тысячи элементов использовать. Это для того, чтобы не писать вычисление sizeof(prime)/sizeof(*prime). Тут уже различные вариации возможны. Главное - алгоритм.

@Thinker · 09.10.2012, 20:10 **[ТС]**

Дополню сюда очень быстрый алгоритм нахождения суммы делителей

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
unsigned long Sum(unsigned long a)
{
   unsigned long sum = 1, k = 1, i;
   if (a == 1)
      return a;
   while ((a & 1) == 0)
   {
      k <<= 1;
      a >>= 1;
   }
   k = (k << 1) - 1;
   if (a == 1)
      return k;
   else
      sum = k;
   for(i = 3; i*i <= a; i += 2)
   {
      k = 1;
      while(a % i == 0)
      {
         k *= i;
         a /= i;
      }
      if (k > 1)
         sum *= ((k * i) - 1)/(i - 1);
   }
   if (a > 1)
      sum *= a + 1;
   return sum;
}

данный алгоритм быстрее обычного цикла от 1 до a в сотни тысяч раз и чем больше число a, тем острее чувствуется разница.

@Thinker · 11.10.2012, 13:54 **[ТС]**

Еще один очень быстрый алгоритм нахождения суммы делителей. Отличается от предыдущего меньшим количеством делений. По скорости одинаковы.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unsigned long Sum(unsigned long a)
{
   unsigned long sum = 1, k = 1, i, p;
   if (a == 1)
      return a;
   while ((a & 1) == 0)
   {
      k <<= 1;
      a >>= 1;
   }
   k = (k << 1) - 1;
   if (a == 1)
      return k;
   else
      sum = k;
   for(i = 3; i*i <= a; i += 2)
   {
      p = k = 1;
      while(a % i == 0)
      {
         k *= i;
         p += k;
         a /= i;
      }
      if (k > 1)
         sum *= p;
   }
   if (a > 1)
      sum *= a + 1;
   return sum;
}

@Pepsy · 13.01.2013, 21:11

Вот такой вопрос: а как вы определяете скорость? не на секундомере же.

@diagon · 13.01.2013, 21:37

Сообщение от Pepsy

не на секундомере же.

Можно и на секундомере. Но вообще, есть такая вещь как ассимптотическая сложность. В исходниках выше она равна O(sqrt(n)).
Можно ее ускорить, если взять более эффективный алгоритм факторизации(метод квадратичного решета, например).

@shalad · 26.02.2013, 15:18

Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте? Хотелось бы его разобрать, но пока что для меня все, что происходит внутри - магия

@Thinker · 11.06.2013, 09:50 **[ТС]**

Сообщение от shalad

Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте?

Пока я его никак не назвал, просто придумал

diagon предлагает еще оптимизировать.

@_Murchik_ · 06.02.2016, 13:26

Thinker, а можно найти четное или не четное количество делителей, ваш алгоритм не проходит по времени

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

Быстрое нахождение количества делителей натурального числа

Решение

Решение

@Pepsy 47 / 32 / 9 Регистрация: 05.01.2013 Сообщений: 307
	13.01.2013, 21:11
	Вот такой вопрос: а как вы определяете скорость? не на секундомере же. 0

@shalad 7 / 7 / 2 Регистрация: 17.05.2010 Сообщений: 122
	26.02.2013, 15:18
	Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте? Хотелось бы его разобрать, но пока что для меня все, что происходит внутри - магия 0

@_Murchik_ 0 / 0 / 1 Регистрация: 11.10.2015 Сообщений: 15
	06.02.2016, 13:26
	Thinker, а можно найти четное или не четное количество делителей, ваш алгоритм не проходит по времени Миниатюры 0