ITGUY27 - Editorial

Problem: CodeChef: Practical coding for everyone

DIFFICULTY:

EASY.

PROBLEM:

The chef was busy in solving algebra, he found some interesting results, that there are many numbers which can be formed by sum of some numbers which are prime. Chef wrote those numbers in dairy. Cheffina came and saw what the chef was doing. Cheffina immediately closed chef’s dairy and for testing chef’s memory, she starts asking numbers and chef needs to answer wheater given number N can be formed by the sum of K prime numbers if it yes then print 1 else print 0.

Program:

#include<bits/stdc++.h> 
using namespace std; 

int main() 
{ 
	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);
   	cout.tie(NULL);
   	int n=100000;
	bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    int t;
    cin>>t;
    while(t--){
	    int N,K;
	    cin>>N>>K;
	    if (N < 2*K)cout<<0<<"\n"; 
	    else if (K == 1){
	    	if(prime[N])cout<<1<<"\n";
	    	else cout<<0<<"\n";
	    }
	    else if (K == 2) 
	    { 
	        if (N%2 == 0)cout<<1<<"\n"; 
	  		else if(prime[N-2])cout<<1<<"\n";
	  		else cout<<0<<"\n"; 
	    } 
	    else cout<<1<<"\n"; 
	}
}

@references Can you please explain the logic of your code?