Expert.
Put your skills to the test.

Problem summary

Count primes in [a,b] whose binary representation can be split into two prime numbers without leading zeros and with bit lengths differing by at most one.

Constraints

1 ≤ a ≤ b ≤ 50000000.

Worked example

Official statement example.

8 109

7

Solution analysis

1. Build a sieve of primes through b using packed bits. Only prime candidates need a split test. A split with right-hand length r extracts left=p>>r and right=p modulo 2^r.
2. If the total bit length is L, balanced pieces require r=L/2 for even L, or r=floor(L/2) and ceil(L/2) for odd L. Require right≥2^(r−1) to exclude leading zeros, then test both pieces in the sieve.
3. For 29=11101₂, the split 11|101 gives primes 3 and 5 with lengths 2 and 3. For 43=101011₂, the equal split 101|011 fails because the right piece has a leading zero. Count each whole prime at most once.

Why it works

Every allowed decomposition has one of the tested right-piece lengths. Bit extraction produces exactly its two pieces and the leading-bit check enforces the representation rule. The sieve identifies primality exactly, so a whole number is counted precisely when at least one legal split exists.

Watch out. A numeric suffix can be prime despite having a forbidden leading zero in the split.,Do not double-count primes with two valid splits.

An independently written complete program with standard headers.

// Key idea: Every allowed decomposition has one of the tested right-piece lengths. Bit extraction
// produces exactly its two pieces and the leading-bit check enforces the representation rule.
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    vector<bool>prime(b+1,true);
    prime[0]=false;
    if(b>=1){
        prime[1]=false;
    }
    for(int p=2;p<=b/p;++p){
        if(prime[p]){
            for(int v=p*p;v<=b;v+=p){
                prime[v]=false;
            }
        }
    }
    int answer=0,length=1,nextPower=2;
    for(int p=1;p<=b;++p){
        if(p==nextPower){
            ++length;
            nextPower*=2;
        }
        if(p<a||!prime[p]){
            continue;
        }
        bool good=false;
        for(int r=length/2;r<=(length+1)/2;++r){
            if(r==0){
                continue;
            }
            int left=p>>r;
            int right=p&((1<<r)-1);
            if(right>=(1<<(r-1))&&prime[left]&&prime[right]){
                good=true;
            }
        }
        if(good){
            ++answer;
        }
    }
    cout<<answer<<'\n';
}