number of positive divisors Algorithm

The number of positive divisors algorithm is a mathematical method used to determine the total count of distinct positive divisors for a given positive integer. Divisors are the numbers that divide the given integer exactly without leaving any remainder. This algorithm is highly useful in number theory, and its applications can be extended to solve various problems in mathematics, cryptography, and computer science. The algorithm is based on the prime factorization concept, which involves breaking down the given integer into its prime factors and then utilizing their powers to calculate the total count of divisors. To execute this algorithm, one must first find the prime factorization of a given integer by dividing it with prime numbers, starting from the smallest prime (2) and moving up. After obtaining the prime factorization, the powers of these prime factors are increased by one and then multiplied together to get the total count of divisors. For example, if the given integer is 28, its prime factorization is 2^2 * 7^1. By increasing the powers by 1, we get (2+1) * (1+1) = 3 * 2 = 6. Thus, the number of positive divisors of 28 is 6, which are 1, 2, 4, 7, 14, and 28. This algorithm is efficient and quick, especially for large numbers, as it eliminates the need to test all possible factors and instead focuses on utilizing the prime factors and their powers to achieve the desired result.
/// C++ Program to calculate number of divisors.

#include<iostream>
#include<vector>

/**
 * This algorithm use the prime factorization approach.
 * Any number can be written in multiplication of its prime factors.
 * Let N = P1^E1 * P2^E2 ... Pk^Ek
 * Therefore. number-of-divisors(N) = (E1+1) * (E2+1) ... (Ek+1).
 * Where P1, P2 ... Pk are prime factors and E1, E2 ... Ek are exponents respectively.
 *
 * Example:-
 * N = 36
 * 36 = (3^2 * 2^2)
 * number_of_positive_divisors(36) = (2+1) * (2+1) = 9.
 * list of positive divisors of 36 = 1, 2, 3, 4, 6, 9, 12, 18, 36.
 *
 * Similarly if N is -36 at that time number of positive divisors remain same.
 *
 * Example:-
 * N = -36
 * -36 = -1 * (3^2 * 2^2)
 * number_of_positive_divisors(-36) = (2+1) * (2+1) = 9.
 * list of positive divisors of -36 = 1, 2, 3, 4, 6, 9, 12, 18, 36.
 *
**/

int number_of_positive_divisors(int n) {
    std::vector<int> prime_exponent_count;
    for (int i=2; i*i <= n; i++) {
        int prime_count = 0;
        while (n % i == 0) {
            prime_count += 1;
            n /= i;
        }
        if (prime_count != 0) {
            prime_exponent_count.push_back(prime_count);
        }
    }
    if (n > 1) {
        prime_exponent_count.push_back(1);
    }

    int divisors_count = 1;

    for (int i=0; i < prime_exponent_count.size(); i++) {
        divisors_count = divisors_count * (prime_exponent_count[i]+1);
    }

    return divisors_count;
}

int main() {
    int n;
    std::cin >> n;
    if (n < 0) {
        n = -n;
    }
    if (n == 0) {
        std::cout << "All non-zero numbers are divisors of 0 !" << std::endl;
    } else {
        std::cout << "Number of positive divisors is : ";
        std::cout << number_of_positive_divisors(n) << std::endl;
    }
}

LANGUAGE:

DARK MODE: