I have came across a coding problem. I am unable to solve the problem. Can anyone help me out:
Panda can do any problem anytime and anywhere. Panda is doing an extensive research on prime numbers. Milinda has got a question for Panda. The only way for Panda to impress Milinda is by solving this question.
Given a number N , find the minimum number of primatic numbers which sum upto N .
A primatic number refers to a number which is either a prime number or can be expressed as power of prime number to itself i.e. primeprime e.g. 4, 27, etc.
Note: 8, 32, etc are not primatic numbers.
Panda is very sad since he is unable to solve the problem. Please help Panda in solving this problem.
The first line will contain two integers: T , the number of test cases.
Each test case consists of a single integer N .
For each query output the minimum number of primatic numbers which can sum upto N .
1 <= T <= 105
2 <= N <= 104
T = 100 , 2 <= N <= 1000 - 20 points
T = 105 , 2 <= N <= 104 - 80 points
- The number 6 can be represented as 2 + 2 + 2, 3 + 3, etc. The smallest one among these is 3 + 3 consisting of 2 primatic numbers.
- The number 3 is itself primatic. Hence the answer is 1.
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB