Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 89, средняя оценка - 4.89
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
#1

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

28.09.2012, 19:47. Просмотров 11573. Ответов 9
Метки нет (Все метки)

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

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;
}
Предлагаю всем желающим попробовать свои силы и написать что-то быстрее представленного выше.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.09.2012, 19:47     Быстрое нахождение количества делителей натурального числа
Посмотрите здесь:
Нахождение количества делителей числа через рекурсию C++
C++ Нахождение наименьшего нечетного натурального делителя k (k≠1) любого заданного натурального числа n
C++ Быстрое нахождение максимального делителя числа
Найти сумму делителей натурального числа C++
Функция - число делителей натурального числа C++
Определить К - количество делителей натурального числа N C++
C++ Вычисление суммы делителей натурального числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
28.09.2012, 21:58     Быстрое нахождение количества делителей натурального числа #2
Цитата Сообщение от Thinker Посмотреть сообщение
#define N 100
N -- это количество простых чисел в нижеследующем массиве что ли?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 22:12  [ТС]     Быстрое нахождение количества делителей натурального числа #3
Цитата Сообщение от yekka Посмотреть сообщение
N -- это количество простых чисел в нижеследующем массиве что ли?
да, именно. массив можно и из тысячи элементов использовать. Это для того, чтобы не писать вычисление sizeof(prime)/sizeof(*prime). Тут уже различные вариации возможны. Главное - алгоритм.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.10.2012, 20:10  [ТС]     Быстрое нахождение количества делителей натурального числа #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Дополню сюда очень быстрый алгоритм нахождения суммы делителей
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
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2012, 13:54  [ТС]     Быстрое нахождение количества делителей натурального числа #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Еще один очень быстрый алгоритм нахождения суммы делителей. Отличается от предыдущего меньшим количеством делений. По скорости одинаковы.
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
47 / 32 / 4
Регистрация: 05.01.2013
Сообщений: 307
13.01.2013, 21:11     Быстрое нахождение количества делителей натурального числа #6
Вот такой вопрос: а как вы определяете скорость? не на секундомере же.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.01.2013, 21:37     Быстрое нахождение количества делителей натурального числа #7
Цитата Сообщение от Pepsy Посмотреть сообщение
не на секундомере же.
Можно и на секундомере. Но вообще, есть такая вещь как ассимптотическая сложность. В исходниках выше она равна O(sqrt(n)).
Можно ее ускорить, если взять более эффективный алгоритм факторизации(метод квадратичного решета, например).
shalad
7 / 7 / 0
Регистрация: 17.05.2010
Сообщений: 122
26.02.2013, 15:18     Быстрое нахождение количества делителей натурального числа #8
Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте? Хотелось бы его разобрать, но пока что для меня все, что происходит внутри - магия
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.06.2013, 09:50  [ТС]     Быстрое нахождение количества делителей натурального числа #9
Цитата Сообщение от shalad Посмотреть сообщение
Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте?
Пока я его никак не назвал, просто придумал diagon предлагает еще оптимизировать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа
Еще ссылки по теме:
Сумма делителей данного натурального числа C++
C++ Среднее арифметическое всех делителей натурального числа
Найти количесво нечетных делителей натурального числа C++
Подсчитать количество делителей данного натурального числа. C++
Найти количество делителей натурального числа, больших K C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
_Murchik_
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 14
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа #10
Thinker, а можно найти четное или не четное количество делителей, ваш алгоритм не проходит по времени
Миниатюры
Быстрое нахождение количества делителей натурального числа   Быстрое нахождение количества делителей натурального числа  
Yandex
Объявления
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru