Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Number of divisors with prime factorization

    A naive approach to finding the number of multiples of a positive integer n is by looping over all the numbers from 1 to n inclusive and counting the number of values that divide n.
    Yet, this approach is very slow. It’s possible to find the number of divisors of n using its prime factors (finding prime factors takes only time).
    Imagine a number is represented as a product of its prime factors:
    We can calculate the number of divisors of n by taking all the exponents, adding 1 to those, and multiplying the resulting exponents together:
    This can be implemented very similarly to how we find all the prime factors of n:
    n = ...
    p, divisors = 1, 1          # prime factor and the number of divisors
    
    while p * p <= n:           # while p <= sqrt(n)
        p += 1                  # Add 1 to the prime factor on each iteration
        if n % p != 0:          # Do nothing if n is not divisible by p
            continue
        
        exp = 0                 # counter for the exponent
        while n % p == 0:       # divide as many times as possible
            n //= p
            exp += 1
        divisors *= exp + 1     # update the product
    
    if n > 1:                   # if p > sqrt(n) => n is a prime factor itself
        divisors *= 2           # add n as a divisor with exponent 1
    print(divisors)

    Challenge: Find the number of divisors of n

    Given an integer n, you are asked to find the number of divisors of n.

    Input

    The first line of the input contains a single integer n (2 ≀ n ≀ ).

    Output

    The program should print the number of divisors of n.

    Examples

    Input
    Output
    8
    4
    17
    2
    2048
    12
    48
    10
    Bonus: Why does taking all the exponents, adding 1 to those, and multiplying the resulting exponents together result in the total number of divisors of n?
    The intuition behind the formula for finding the number of divisors of n comes from considering the number of divisors as the number of combinations of its prime factors. The exponent of each factor is the number of times it can be used in the product that forms the divisor of n. Adding 1 to each exponent allows for including combinations that include 0 of each prime factor, which corresponds to including n itself and 1 as divisors of n. The final result of multiplying the (exponent + 1) of each prime factor together counts the number of combinations of all prime factors and gives the total number of divisors of n.
    Β 

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue