Question Name:PRIME NUMBERS AGAIN

#include <iostream>
using namespace std;
int main()
{

int avi,b,i;
  cin>>avi;
  for(i=0;i<avi;i++) { 
    cin>>b;
    if(b==1) 
    { 
      cout<<0<<endl; 
    } 
    if( b==3 || b==4 || b==2 || b==5 || b==7) 
    { 
      cout<<1<<endl;
    } 
    if( b==6||b==9||b==8||b==10||b==21)
    { 
      cout<<2<<endl;
    } 
  } 
    
	return 0;
}
  • Problem Description
    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. prime^prime 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 <= 10^5
    2 <= N <= 10^4

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

    Subtask 2:
    T = 10^5, 2 <= N <= 104 – 80 points
  • Test Case 1
    Input (stdin)2
    6 3
    Expected Output2
    1
  • Test Case 2
    Input (stdin)11
    4 2 1 3 5 7 6 9 8 10 21
    Expected Output1
    1
    0
    1
    1
    1
    2
    2
    2
    2
    2

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.