AEASYP - Editorial

NOTE:

This editorial belongs to a closed contest held for Kendriya Vidyalaya, Aurangabad school. Also, for the domain of students participating, the problems were kept simple. So, you can safely skip this editorial.

PROBLEM LINK:

Practice
Contest

Author: Abhinav Kaushlya
Tester: Abhinav Kaushlya
Editorialist: Abhinav Kaushlya

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

The problem is to find the number of prime numbers between the given range such that the sum of their digits is even.

QUICK EXPLANATION:

We can do this multiple ways. One way could be to precompute the number of prime numbers from lower to upper bound, finding the ones whose digit sum is even and map them into their range.

EXPLANATION:

We will solve each query in O(1). We will precompute the number of such prime numbers whose digit sum is even. It could be further optimized but here we will stick to this approach. First we will find all the prime numbers through “sieve of eratosthenes” between 1 and 10^3. After which we will go through each prime number and if the digit sum is even then we would add 1 to the prvious count of such numbers, else we will simply keep the count same for the current range as well.

Please refer to the solution for more details or just ask me sometime in school :smiley:

ALTERNATIVE SOLUTION:

There could be several ways of solving this problem. But seeing the domain of participating students we kept it simple enough to solve.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.