Panda Prime problem

help
, , ,
1

I have came across a coding problem. I am unable to solve the problem. Can anyone help me out:
PROBLEM STATEMENT

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.

Input Format:
The first line will contain two integers: T , the number of test cases.
Each test case consists of a single integer N .

Output Format:
For each query output the minimum number of primatic numbers which can sum upto N .

Constraints:
1 <= T <= 105
2 <= N <= 104

Subtask 1:
T = 100 , 2 <= N <= 1000 - 20 points

Subtask 2:
T = 105 , 2 <= N <= 104 - 80 points

SAMPLE INPUT

2

6

3

SAMPLE OUTPUT

2

1

Explanation

  1. 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.
  2. 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

2

The only possible answers are among 1 2 and 3.
1 - When the number is prime or power of some prime.
2 - When it is even
3 - When it is odd.

That’s all.

This is based on Goldbach Conjecture.

So just check in above sequence.

Now the only problem remains is when a number is odd and we need to check if it can be written as sum of two prime powers.
Now if it can be written then one of the numbers among the two must be a power of two.
This is because,
odd + even = odd (ex - 5 + 4 = 9)
So since the number is odd then one of the numbers in the addition must be even. And 2 is the only prime which can give even powers.
So we just calculate powers of two beforehand and check for this condition.

If we did not find any such combination then the answer is 3.