DCP-116: “What is that” and Prime Back to All Problems

Medium Math > Number Theory

This time “Why I am“ is teaching his little sister “What is that”. The task is “Why I am“ will read a number and “What is that” will write this number. But “What is that” is a prime lover. That's why she does not directly write that number, write as a sum of minimum number of prime. “Why I am“ is now curious what should be the minimum number of prime needed to write that number. Your task is “Why I am“ will give a number and you will tell us what is the minimum number of prime to write that number. Input: ------ Input starts with an integer **T (1<=100)**, denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 10^12)**. Output: ------- For each test case, print a line containing the minimum number of prime to write that number. Sample Input ------------ 3 2 6 27 Sample Output ------------- 1 2 3

Problem Setter:

MD Musfiqur Rahman Sanim

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 nuhu_iu Cpp14 0.01s
02 Morass Cpp14 0.01s
03 feodorv C 0.02s
04 tariqiitju Cpp14 0.02s
05 Robbinb1993 Cpp 0.03s
06 anik_JU Cpp14 0.05s
07 subhashis_cse Cpp 0.05s
08 sazal_dev Cpp14 0.05s
09 mir003 Cpp14 0.05s
10 duronto20 Cpp14 0.07s
11 murad_al_wajed Cpp14 0.09s
12 emrul Cpp14 0.09s
13 Riaz_BSMRSTU Cpp 0.10s
14 rayhan50001 Cpp14 0.12s
15 orpib Cpp14 0.14s
16 RandyWaterhouse Python3 0.16s
17 robin_aust Cpp14 0.17s
18 _dipu Cpp14 0.21s
19 Zeronfinity Cpp14 0.33s
20 moinul_shaon Cpp14 0.42s
21 mamun4122 Cpp14 0.42s
22 dipta007 Cpp14 0.43s
23 Koushik_12 Cpp14 0.46s
24 showmic Cpp14 0.46s
25 shuvo_iu Cpp14 0.47s
26 prantacse14 Cpp14 0.47s
27 Jakir_Hossain_Sust Cpp14 0.47s
28 as_couple Cpp14 0.48s
29 KIRIN_36 Cpp14 0.49s
30 anowar1112 Cpp14 0.50s
31 mahbubcseju Cpp14 0.51s
32 alhelal_cse Cpp14 0.51s
33 nmunim Cpp14 0.52s
34 PKP_007 Cpp14 0.52s
35 nasif2587 Cpp14 0.53s
36 ISMAIL_HOSSAIN Cpp14 0.53s
37 Skyfall009 Cpp14 0.53s
38 moin132 Cpp14 0.54s
39 Fahim_Ahmed Cpp14 0.55s
40 INUA Cpp14 0.55s
41 rafsan_rana Cpp14 0.55s
42 rajdipsaha Cpp14 0.56s
43 Double_O Cpp14 0.57s
44 Jobayer__ Cpp14 0.57s
45 Mahmudul_Tushar Cpp14 0.58s
46 clcrr Cpp14 0.58s
47 ksohan Cpp14 0.59s
48 khatribiru Cpp14 0.59s
49 codehead Cpp14 0.59s
50 MASUDUR_RAHMAN Cpp14 0.62s

Your feedback is our precious!

Or call +88 02 9853138 for support