Un număr natural în baza 10 se numește prețios dacă numărul de cifre ale sale din baza 2 este număr prim.

Cerința

Se dă un interval [a,b].Determinați câte numere prețioase se află în acest interval.

Date de intrare

Programul citește de la tastatură numerele a și b.

Date de ieșire

Programul va afișa pe ecran numărul x, reprezentând numărul de numere prețioase din intervalul dat.

Restricții și precizări

• 1 ≤ a,b ≤ 10000000000000000000

Exemplu

Intrare

1 4

Ieșire

3

Explicație

Cele 3 numere prețioase sunt 2 3 4.

#include <bits/stdc++.h>
using namespace std;
unsigned long long start, stop;
unsigned long long a, b, i, nr, p = 1;
bool prim(long long x)
{
    bool ok = true;
    long long i;
    if(x == 0 or x == 1) return false;
    for(i = 2; i * i <= x; i ++)
    if(x % i == 0)
    {
        ok = false;
        break;
    }
    return ok;
}

int main()
{
    cin >> a >> b;
    start = log2(a) + 1;
    stop = log2(b);
    for(i = 1; i <= start; i ++)
        p = p * 2;
    if(prim(start))
    {
        nr = nr + p - a;
    }
    for(i = start; i < stop; i ++)
        if(prim(i + 1))
        {
            nr = nr + p;
            p = p * 2;
        } else p = p * 2;
    if(prim(stop + 1)) nr = nr + b - p + 1;
    cout << nr << " ";
    return 0;
}