Does Ash Loves Pikachu
Prerequisite:
Prime Factorization
Basic Implementation
Here we need to check if a number is prime or composite by using some predefined set of actions, and to make sure that whether the given number is prime or not?
We all know that a number n is prime if it is not divisible by any number from 2 to n-1, so we can check that every number is prime or not by simply dividing it all the numbers from 2 to n-1 but here is a twist that we can’t ask more than 55 queries in total for a given number between 2 to 400 (inclusive) and any query must not exceed 400.
So if we make an array of all the prime numbers till 400, then we can iterate over this array and can check if the hidden number is divisible by any of them let’s say p and if it is then we’ll check that if the given hidden number is divisible by p² or not and we’ll maintain a counter and after asking the required queries we’ll come out of the loop and will check if the value of our counter is less than 2 or equal to 2.
If it’s equal to 2 then we’ll simply output 0 as it’s composite and 1 if the counter is less than 2 (i.e. it’s prime).
Here is the solution to the problem in Cpp
