Check if a number is prime - a bit faster
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
nand counting the number of divisors.
- Looping over the numbers from 2 up to
nand stopping as soon as it found a divisor.
There are several small tweaks we can do to optimize the procedure:
Optimization 1:
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).Optimization 2:
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.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 |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 0.5 seconds
Memory limit: 512 MB
Output limit: 1 MB