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
      • 19
        BFS

  • Prime factorization

    Any positive integer n ≥ 2 can be represented as a product of prime numbers:
    There are many applications for finding prime factors when dealing with numbers. It’s possible to easily count the number of divisors of that number, get an intuition on the greatest common divisors (GCD) and least common multiples (LCM) for two numbers, etc.
    To represent a number n (say 300) as a product of its prime factors one can start from the smallest prime number p (2) and in case n is divisible, keep dividing n by p as long as it’s possible to do so (300 / 2 = 150, 150 / 2 = 75).
    After that increase p by 1 (p = 3) and try dividing n by the new p. In case it’s possible, divide n by p as long as it’s divisible (75 / 3 = 25).
    Then increase p by 1 (p = 4) and try dividing n by the new p. It’s not possible to divide n by any non-prime number as n was divided by smaller prime numbers exhaustively. In our case, 300 is divisible by 4, but 75 is not as we have divided 300 by 2 (which is a divisor of 4) before this several times. So, because we have exhausted all the 2s, the future numbers won’t be divisible by 4, 6, 8, and any multiple of 2. As this process goes from the smallest number to the largest one, we can be certain that we are left with only prime numbers to divide the remaining number.
    During the next step, we increase the divisor by 1 again (p = 5) and try to divide n by the new p (75 / 5 = 5, 5 / 5 = 1). This process continues until the divisor is larger than . If we have reached a point when the divisor is larger than ⇒ the remaining n is a prime number itself and we can take it as one of the divisors in our final answer.
    Therefore, for our example, 300 can be represented as .
    n = ...                              # Represent n as a product of primes
    p, divisors, powers = 1, [], []      # prime factor, divisors, and their exponents
    
    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
        
        divisors.append(p)               # n % p == 0 => add p as a prime factor
        powers.append(0)                 # the exponent is initially 0
        while n % p == 0:                # divide as many times as possible
            n //= p
            powers[-1] += 1              # increase the exponent by 1 on each iteration
    
    if n > 1:                            # if p > sqrt(n) => n is a prime factor itself
        divisors.append(n)               # add n as a divisor
        powers.append(1)                 # with an exponent of 1
    
    print(list(zip(divisors, powers)))   # print factors and their exponents together
    On each iteration of the algorithm, we divide the number by its prime factor if possible, and keep dividing it by simultaneously increasing the exponent by 1 on each iteration.
    Let’s run a simulation of the algorithm on several numbers:
    n = 24
    1. p = 2, n = 24 (we increased p from 1 to 2 at the beginning of the loop) n % 2 == 0divisors = [2], powers = [0] n //= 2n = 12, powers = [1] n //= 2n = 6, powers = [2] n //= 2n = 3, powers = [3]
    1. p = 3, n = 3 ⇒ stop the while loop as p * p = 9 which is greater than 2
    1. n > 1divisors = [2, 3], powers = [3, 1]
    n = 75
    1. p = 2, n = 75
    1. p = 3, n = 75 n % 3 == 0divisors = [3], powers = [0] n //= 3n = 25, powers = [1]
    1. p = 4, n = 25
    1. p = 5, n = 25 n % 5 == 0divisors = [3, 5], powers = [1, 0] n //= 5n = 5, powers = [1, 1] n //= 5n = 1, powers = [1, 2]
    1. p * p > n ⇒ stop the while loop ⇒ divisors = [3, 5], powers = [1, 2]
    n = 84
    1. p = 2, n = 84 n % 2 == 0divisors = [2], powers = [0] n //= 2n = 42, powers = [1] n //= 2n = 21, powers = [2]
    1. p = 3, n = 21 n % 3 == 0divisors = [2, 3], powers = [2, 0] n //= 3n = 7, powers = [2, 1]
    1. p * p > n ⇒ stop the while loop
    1. n > 1divisors = [2, 3, 7], powers = [2, 1, 1]
    n = 31
    1. p = 2, n = 31
    1. p = 3, n = 31
    1. p = 4, n = 31
    1. p = 5, n = 31
    1. p = 6, n = 31
    1. p * p > n ⇒ stop the while loop
    1. n > 1divisors = [31], powers = [1]

    Challenge

    Given an integer n, you are asked to find its largest prime factor.

    Input

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

    Output

    The program should print the largest prime factor of n.

    Examples

    Input
    Output
    8
    2
    24
    3
    75
    5
    31
    31
    Bonus: Why don’t we check for only prime numbers?
    Our current implementation of the algorithm runs through all the numbers 2, 3, 4, … up to . Wouldn’t it make more sense to iterate over only prime numbers?
    At the first glance, it seems like a reasonable idea (and there might be some problems where this can be implemented). Yet, the procedure of finding all the prime numbers up to will take more iterations than ( to be more precise). So, finding the prime numbers up to the needed point will be more time-consuming than iterating over all the possible numbers up to and checking if n is divisible by that number.
    Can you think of a scenario where finding out the prime numbers beforehand and iterating over them to get the prime factors after might be more optimal?
     

    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