# 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`

`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]`

`p = 3`

,`n = 3`

β stop the while loop as`p * p = 9`

which is greater than 2

`n > 1`

β`divisors = [2, 3]`

,`powers = [3, 1]`

`n = 75`

`p = 2`

,`n = 75`

`p = 3`

,`n = 75`

`n % 3 == 0`

β`divisors = [3]`

,`powers = [0]`

`n //= 3`

β`n = 25`

,`powers = [1]`

`p = 4`

,`n = 25`

`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]`

`p * p > n`

β stop the while loop β`divisors = [3, 5]`

,`powers = [1, 2]`

`n = 84`

`p = 2`

,`n = 84`

`n % 2 == 0`

β`divisors = [2]`

,`powers = [0]`

`n //= 2`

β`n = 42`

,`powers = [1]`

`n //= 2`

β`n = 21`

,`powers = [2]`

`p = 3`

,`n = 21`

`n % 3 == 0`

β`divisors = [2, 3]`

,`powers = [2, 0]`

`n //= 3`

β`n = 7`

,`powers = [2, 1]`

`p * p > n`

β stop the while loop

`n > 1`

β`divisors = [2, 3, 7]`

,`powers = [2, 1, 1]`

`n = 31`

`p = 2`

,`n = 31`

`p = 3`

,`n = 31`

`p = 4`

,`n = 31`

`p = 5`

,`n = 31`

`p = 6`

,`n = 31`

`p * p > n`

β stop the while loop

`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.4 seconds

Memory limit: 512 MB

Output limit: 1 MB