Below is the solution for Prime sum question on Hackerank.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k==’-‘){m=1;break;}if(‘0′<=k&&k<=’9’){*x=k-‘0’;break;}}for(;;){mygc(k);if(k<‘0’||k>’9’)break;*x=(*x)*10+k-‘0′;}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k==’-‘){m=1;break;}if(‘0′<=k&&k<=’9’){*x=k-‘0’;break;}}for(;;){mygc(k);if(k<‘0’||k>’9’)break;*x=(*x)*10+k-‘0′;}if(m)(*x)=-(*x);}
void writer(const char c[]){int i;for(i=0;c[i]!=’\0’;i++)mypc(c[i]);}
/* 64?2????leading zero??? */
int ullNumberOfLeadingZerosTable[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int ullNumberOfLeadingZeros(ull x){
int res=56; unsigned xl=x, xh=x>>32;
if(xh) res -= 32, xl = xh;
if(xl&0xffff0000U) res -= 16, xl >>= 16;
if(xl&0x0000ff00U) res -= 8, xl >>= 8;
return res + ullNumberOfLeadingZerosTable[xl];
}
/* (x*y)%m ???? (?? x,y < m) */
ull ullMultipleMod(ull x, ull y, ull m){
int k,loop=2;
ull xlo,xhi,ylo,yhi,rlo,rhi,d1,d2,a,q,r,mask=0xffffffffULL;
if(m<=mask) return (x*y)%m; xlo=(x&mask); xhi=(x>>32);
ylo=(y&mask); yhi=(y>>32);
rhi=xhi*yhi; rlo=xlo*ylo;
a=(rlo>>32)+xhi*ylo;
rhi+=(a>>32); a&=mask; a+=xlo*yhi; rhi+=(a>>32);
rlo = (rlo&mask) | ((a&mask)<<32);
k = ullNumberOfLeadingZeros(m);
rhi = (rhi<<k)|(rlo>>(64-k));
rlo<<=k; m<<=k; d1=(m>>32); d2=(m&mask);
while(loop–){
r = rhi/d1*d2;
rhi = ( (rhi%d1 << 32) | (rlo>>32) );
rlo = ( (rlo&mask) << 32 );
if(rhi<r) rhi+=m-r; else rhi-=r; if(rhi>m) rhi+=m;
}
return rhi>>k;
}
/* (x^k)%m */
ull ullPowMod(ull x, ull k, ull m){
ull res;
if(k==0) return 1;
res = ullPowMod(x,k/2,m);
res = ullMultipleMod(res,res,m);
if(k%2) res = ullMultipleMod(res,x,m);
return res;
}
ull unsignedMillerRabinSuspectPow(int a, unsigned k, unsigned n){
ull p=1; unsigned bit;
for (bit=0x80000000U;bit;bit>>=1) {
if(p>1) p=(p*p)%n;
if(k&bit) p=(p*a)%n;
}
return p;
}
int unsignedMillerRabinSuspect(int b, unsigned n){
unsigned i,t=0,u=n-1; ull now, next;
while(!(u&1)) t++, u>>=1;
now = unsignedMillerRabinSuspectPow(b, u, n);
for(i=1;i<=t;i++){
next=(now*now)%n;
if(next==1 && now!=1 && now!=n-1) return 0;
now=next;
}
return next==1;
}
int unsignedMillerRabin(unsigned n){
if(n<=1)return 0; if(n<=3)return 1; if(!(n&1))return 0;
if(!unsignedMillerRabinSuspect(2,n)) return 0;
if(n<=1000000){ if(!unsignedMillerRabinSuspect(3,n)) return 0; } else { if(!unsignedMillerRabinSuspect(7,n)) return 0; if(!unsignedMillerRabinSuspect(61,n)) return 0; } return 1; } ull ullMillerRabinSuspectPow(ull a, ull k, ull n){ ull p=1, bit; for (bit=0x8000000000000000ULL;bit;bit>>=1) {
if(p>1) p=ullMultipleMod(p,p,n);
if(k&bit) p=ullMultipleMod(p,a,n);
}
return p;
}
int ullMillerRabinSuspect(ull b, ull n){
ull i, t=0, u=n-1, now, next;
while(!(u&1)) t++, u>>=1;
now = ullMillerRabinSuspectPow(b, u, n);
for(i=1;i<=t;i++){
next=ullMultipleMod(now,now,n);
if(next==1 && now!=1 && now!=n-1) return 0;
now=next;
}
return now==1;
}
int ullMillerRabin(ull n){
int i,lim;
if(n<(1ULL<<32)) return unsignedMillerRabin(n);
if(!(n&1)) return 0;
if(n < 341550071728321ULL) lim=17; else lim=29;
if(!ullMillerRabinSuspect(2,n)) return 0;
for(i=3;i<=lim;i+=2) if(!ullMillerRabinSuspect(i,n)) return 0;
return 1;
}
int solve(ll N, ll K, int r=0){
if(N==0 && K==0) return 1;
if(K==0) return 0;
if(K==1){
if(ullMillerRabin(N)) return 1;
return 0;
}
if(N < 2*K) return 0; if(N%2==0 && N>=2*K) return 1;
if(r==0){
if(solve(N-2, K-1, 1)) return 1;
if(solve(N-3, K-1, 1)) return 1;
}
return 0;
}
int main(){
int i, j;
int T;
ll N, K;
reader(&T);
while(T–){
reader(&N); reader(&K);
if(solve(N,K)) writer(“Yes\n”); else writer(“No\n”);
}
return 0;
}
This it the solution for the question: Prime Sum