DEBNPRM - Editorial

dynamic-programming
igni2018
sieve

#1

Problem link:##

Contest , Practice

Setter: Souradeep Paul

Tester: Debjit Datta
##Difficulty:##
Easy
##Prerequisites:##
Dynamic Programming, Prime-sieve

##Explanation:##
Given a number, we have to find if its prime. If not we add the first prime number to it and
check if its prime and then the second and so on until the sum becomes prime.

We use prime sieve and store all the prime numbers as false in a boolean array and composite
numbers as true. Along with that we keep a list of all prime numbers upto 10^7.
We check if the given number is prime and if not, we add the first number from the list to it
and check again. The process goes on until we find a prime number.

##Author’s and Tester’s Solution:##
Author’s solution is here

Tester’s solution is here