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

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

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

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

28.09.2012, 19:47. Просмотров 11774. Ответов 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++
Здравствуйте, я решал задачу на нахождение кол-ва делителей числа через рекурсию, вот код: void Rec(int x, int y, int Am) { if...

Нахождение наименьшего нечетного натурального делителя k (k≠1) любого заданного натурального числа n - C++
Помогите с этой задачой: Подпрограммы Составить функцию для нахождения наименьшего нечетного натурального делителя k (k≠1) любого...

Быстрое нахождение максимального делителя числа - C++
Всем привет! Столкнулся с такой проблемой, у меня дано число n \leq 10 ^ 18. Для использования моего алгоритма, мне нужно быстро найти...

Функция - число делителей натурального числа - C++
We define the function f(x) = the number of divisors of x. Given two integers a and b (a ≤ b), please calculate f(a) + f(a+1) + ... + f(b)....

Определить К - количество делителей натурального числа N - C++
дано натуральное число N. Определить К-количество делителей этого числа не превышающих его (N-12, его делители 1 2 3 4 6 K=5) N-целое...

Сумма делителей данного натурального числа - C++
Задание: Написать подпрограмму, которая вычисляет сумму делителей данного натурального числа Добавлено через 1 час 26 минут 24...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
28.09.2012, 21:58 #2
Цитата Сообщение от Thinker Посмотреть сообщение
#define N 100
N -- это количество простых чисел в нижеследующем массиве что ли?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 22:12  [ТС] #3
Цитата Сообщение от yekka Посмотреть сообщение
N -- это количество простых чисел в нижеследующем массиве что ли?
да, именно. массив можно и из тысячи элементов использовать. Это для того, чтобы не писать вычисление sizeof(prime)/sizeof(*prime). Тут уже различные вариации возможны. Главное - алгоритм.
Thinker
Эксперт C++
4225 / 2199 / 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++
4225 / 2199 / 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
1929 / 1195 / 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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.06.2013, 09:50  [ТС] #9
Цитата Сообщение от shalad Посмотреть сообщение
Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте?
Пока я его никак не назвал, просто придумал diagon предлагает еще оптимизировать.
_Murchik_
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 14
06.02.2016, 13:26 #10
Thinker, а можно найти четное или не четное количество делителей, ваш алгоритм не проходит по времени
Миниатюры
Быстрое нахождение количества делителей натурального числа   Быстрое нахождение количества делителей натурального числа  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2016, 13:26
Привет! Вот еще темы с ответами:

Найти сумму делителей натурального числа - C++
4. Нахождение суммы делителей натурального числа (само число и единицу в качестве делителей не рассматривать).

Вычисление суммы делителей натурального числа - C++
В задаче требуется описать функцию для вычисления суммы делителей натурального числа, и с помощью нее в интервале от 1 до 10000 найти все...

Найти сумму четных делителей натурального числа - C++
пишу вот так , но не пойму до конца логику расчетов...объясните что забыл? #include &lt;iostream&gt; #include &lt;cmath&gt; #include...

Среднее арифметическое всех делителей натурального числа - C++
Составить программу нахождения среднего арифметического значения всех делителей заданного натурального числа N(N&lt;=1000), кратных 3 и 4...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
06.02.2016, 13:26
Ответ Создать тему
Опции темы

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