Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
number_of_positive_divisors.cpp File Reference

C++ Program to calculate the number of positive divisors. More...

#include <cassert>
#include <iostream>
Include dependency graph for number_of_positive_divisors.cpp:

Functions

int number_of_positive_divisors (int n)
 
void tests ()
 
int main ()
 

Detailed Description

C++ Program to calculate the number of positive divisors.

This algorithm uses the prime factorization approach. Any positive integer can be written as a product of its prime factors.
Let \(N = p_1^{e_1} \times p_2^{e_2} \times\cdots\times p_k^{e_k}\) where \(p_1,\, p_2,\, \dots,\, p_k\) are distinct prime factors of \(N\) and \(e_1,\, e_2,\, \dots,\, e_k\) are respective positive integer exponents.
Each positive divisor of \(N\) is in the form \(p_1^{g_1}\times p_2^{g_2}\times\cdots\times p_k^{g_k}\) where \(0\le g_i\le e_i\) are integers for all \(1\le i\le k\).
Finally, there are \((e_1+1) \times (e_2+1)\times\cdots\times (e_k+1)\) positive divisors of \(N\) since we can choose every \(g_i\) independently.

Example:
\(N = 36 = (3^2 \cdot 2^2)\)
\(\mbox{number_of_positive_divisors}(36) = (2+1) \cdot (2+1) = 9\).
list of positive divisors of 36 = 1, 2, 3, 4, 6, 9, 12, 18, 36.

Similarly, for N = -36 the number of positive divisors remain same.

Function Documentation

◆ main()

int main ( void  )

Main function

81  {
82  tests();
83  int n;
84  std::cin >> n;
85  if (n == 0) {
86  std::cout << "All non-zero numbers are divisors of 0 !" << std::endl;
87  } else {
88  std::cout << "Number of positive divisors is : ";
90  }
91  return 0;
92 }
Here is the call graph for this function:

◆ number_of_positive_divisors()

int number_of_positive_divisors ( int  n)

Function to compute the number of positive divisors.

Parameters
nnumber to compute divisors for
Returns
number of positive divisors of n (or 1 if n = 0)
33  {
34  if (n < 0) {
35  n = -n; // take the absolute value of n
36  }
37 
38  int number_of_divisors = 1;
39 
40  for (int i = 2; i * i <= n; i++) {
41  // This part is doing the prime factorization.
42  // Note that we cannot find a composite divisor of n unless we would
43  // already previously find the corresponding prime divisor and dvided
44  // n by that prime. Therefore, all the divisors found here will
45  // actually be primes.
46  // The loop terminates early when it is left with a number n which
47  // does not have a divisor smaller or equal to sqrt(n) - that means
48  // the remaining number is a prime itself.
49  int prime_exponent = 0;
50  while (n % i == 0) {
51  // Repeatedly divide n by the prime divisor n to compute
52  // the exponent (e_i in the algorithm description).
53  prime_exponent++;
54  n /= i;
55  }
56  number_of_divisors *= prime_exponent + 1;
57  }
58  if (n > 1) {
59  // In case the remaining number n is a prime number itself
60  // (essentially p_k^1) the final answer is also multiplied by (e_k+1).
61  number_of_divisors *= 2;
62  }
63 
64  return number_of_divisors;
65 }

◆ tests()

void tests ( )

Test implementations

70  {
71  assert(number_of_positive_divisors(36) == 9);
72  assert(number_of_positive_divisors(-36) == 9);
73  assert(number_of_positive_divisors(1) == 1);
74  assert(number_of_positive_divisors(2011) == 2); // 2011 is a prime
75  assert(number_of_positive_divisors(756) == 24); // 756 = 2^2 * 3^3 * 7
76 }
Here is the call graph for this function:
tests
void tests()
Definition: number_of_positive_divisors.cpp:70
std::cout
std::endl
T endl(T... args)
number_of_positive_divisors
int number_of_positive_divisors(int n)
Definition: number_of_positive_divisors.cpp:33
std::cin