Suppose a program that checks primality is currently being used in the production of a large company. Yet, as the company scales rapidly and the number of users increases, so does the number of requests to your code. They ask you to optimize it and make it a bit faster so that the company is able to handle a load of new users coming rapidly.
Your previous solution was most likely
Looping over the numbers from 2 up to n and counting the number of divisors.
Looping over the numbers from 2 up to n and stopping as soon as it found a divisor.
There are several small tweaks we can do to optimize the procedure:
Instead of looking at all the numbers from 2 to n, we can check if n is divisible by 2 and then check for only the odd numbers. If the number is not divisible by 2, then there is no need to check for all the larger even numbers (4, 6, 8, 10, 12, etc).
Instead of looping from 2 up to n, we can loop up to n/2 as the smallest possible divisor is 2 ⇒ we won’t be able to find any divisors larger than n/2.
We can combine optimizations 1 and 2. As a result, the candidates will be the odd numbers up to n/2. There are about n/4 such numbers so the code will be 4 times more effective than a plain linear check.
These optimizations will make the code a bit faster but in terms of complexity, the algorithm still performs a linear search for divisors. So, as n increases, the algorithm will do proportionally more operations. We’ll discuss how to drastically optimize the primality checking so that it doesn’t do more work proportional to the increase of n later.
The first line of the input contains a single integer n (1 ≤ n ≤ ).
The program should print Yes in case n is prime and No otherwise.