**PROBLEM LINKS:**

**Note:** submissions are facing internal errors

**Difficulty:**

Medium

**Pre-requirements:**

Primality Test

**Problem:**

There are branches numbered from **2** to **X**. Squirrels lie on the branch numbers from **2** to **P**.

Squirrels can jump on to multiples of their branch numbers.

Find the highest branch number in the range **2** to **X** that no squirrel can reach.

**2**<=**P**<=**X**<=**10 ^{9}**

**Explanation:**

The required branch number should be the highest number in the range **2** to **X** and it should not be divisible by any number in the range **2** to **P**.

Let us decrease **X** until it is not divisible by any of the numbers in the range **2** to **P** (or atmost **sqrt(X)** )

Even though **X** can be upto **10 ^{9}**, this approach works because the prime gap of numbers less than billion doesn’t exceed 300 and we’re gonna factorize no more than 300 numbers in total. Therefore the complexity is

**300*sqrt(10**

^{9})**Authors Solution:**

can be found here