Algorithms and Data Structures

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 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ stop the while loop as p * p = 9 which is greater than 2
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 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 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ stop the while loop
  1. n > 1 ⇒ divisors = [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 > 1 ⇒ divisors = [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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in