# Check if a number is prime - fast

So far, finding out if a number

`n`

is prime or not was done through basically a linear search of divisors. This means that if we increased `n`

, the number of operations to find out if `n`

is prime or not would increase proportionally (with some constant multiplied). So, if considering the worst-case scenarios (all the cases when the number `n`

was a prime number - 51, 107, etc) - our algorithm was doing approximately `n/4`

operations to check `n`

for primality.This means that when increasing

`n`

10 times, the algorithm would perform 10 times more operations. If we increase `n`

100 times, the algorithm would perform 100 times more operations. This means that our algorithm is performing proportionally to `n`

. Is there a way to do the checking faster? Seems like there is still a lot of redundant checking done.Β

**The**

**approach:**

Imagine the number

`n`

has a divisor `d`

. This means that

`n`

is divisible by `d`

and both `d`

and

are whole numbers. Moreover, either `d`

or

is less than or equal to

. So, when checking for primality we can actually loop up until reaching the

instead of

. Weβre only interested in checking if a number is divisible by any other number than 1 or `n`

itself, so we can check for the smallest of `d`

or

. Therefore, as one or the other is smaller than

, we can loop until reaching

and stop there.This is a huge improvement! Doing

operations instead of `n`

is a huge difference. Imagine an algorithm that had to work for 10 years (3650 days) to complete a calculation. In case itβs optimized to do

operations instead of `n`

, it would only take it 2 months (61 days) to do so.Β

## Are there better algorithms to check the primality of a number?

Yes! You can read more about them on Algorithms for Competitive Programming. There are algorithms that grow (do more operations as

`n`

increases) logarithmically instead of

. Input

The first line of the input contains a single integer

`n`

(1 β€ n β€ ). Output

The program should print

`Yes`

in case `n`

is prime and `No`

otherwise. Examples

Input | Output |

1 | No |

11 | Yes |

353557 | Yes |

34134741 | No |

902468477 | No |

Β

#### Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB