All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Prime Numbers Again
Tag(s):

Ad-Hoc, Dynamic Programming

Problem
Editorial
Analytics

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.

enter image description here

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Dandi March '15

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?