Timus: [2070. Interesting Numbers]

#include <stdio.h>

#define MAX_N 1000000

int A[((MAX_N - 2) / 2 + 31) >> 5];

int test(int x)
{
    return A[x >> 5] & (1 << (x & 31));
}

void set(int x)
{
    A[x >> 5] |= 1 << (x & 31);
}

int primes[78498] = {2};

int N = 1;

void initialize()
{
    for (int i = 0; 4 * i * i + 12 * i + 9 <= MAX_N; ++i)
    {
        if (!test(i))
        {
            for (int z = 2 * i * i + 6 * i + 3; 2 * z + 3 <= MAX_N; z += 2 * i + 3)
            {
                set(z);
            }
        }
    }
    for (int i = 0; 2 * i + 3 <= MAX_N; ++i)
    {
        if (!test(i))
        {
            primes[N++] = 2 * i + 3;
        }
    }
}

long long L, R;

void input() {
    scanf("%lld%lld", &L, &R);
}

long long check(int p)
{
    int k = 0;
    long long z = 1;
    long long ans = 0;
    for (int i = 1; i < N; ++i)
    {
        while (k + 1 < primes[i])
        {
            z *= p;
            ++k;
            if(z > R)
            {
                return ans;
            }
        }
        ans += z >= L;
    }
    return ans;
}

long long solve()
{
    long long ans = R + 1 - L;
    for (int i = 0; i < N && primes[i] * primes[i] <= R; ++i)
    {
        ans -= check(primes[i]);
    }
    return ans;
}



int main() {
    initialize();
    input();
    printf("%lld\n", solve());
    return 0;
}